Submission #3017158


Source Code Expand

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int M;
    static int D;
    static int[] A;

    static int D_MAX_BIT;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        D = sc.nextInt();
        A = sc.nextIntArray(M);

        PrintWriter pw = new PrintWriter(System.out);
        for (int each : solve()) {
            pw.println(each);
        }
        pw.flush();
    }

    static int[] solve() {
        D_MAX_BIT = Integer.toBinaryString(D).length();

        int[] B = new int[N];
        for (int i = 0; i < N; i++) {
            B[i] = i;
        }
        for (int a : A) {
            int t = B[a];
            B[a] = B[a-1];
            B[a-1] = t;
        }

        int[] T = new int[N];
        for (int i = 0; i < N; i++) {
            int b = B[i];
            T[b] = i;
        }

        int[][] TS = new int[D_MAX_BIT][];
        TS[0] = T;
        for (int b = 1; b < D_MAX_BIT; b++) {
            int[] prev = TS[b-1];
            int[] curr = new int[N];

            for (int i = 0; i < N; i++) {
                // i -> prev[i] -> prev[prev[i]]
                curr[i] = prev[prev[i]];
            }
            TS[b] = curr;
        }

        int[] ANS = new int[N];
        for (int i = 0; i < N; i++) {
            ANS[i] = calc(i, TS) + 1;
        }
        return ANS;
    }

    static int calc(int i, int[][] TS) {
        int cur = i;
        for (int b = 0; b < D_MAX_BIT; b++) {
            if( (D & 1 << b) > 0 ) {
                cur = TS[b][cur];
            }
        }
        return cur;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}

Submission Info

Submission Time
Task D - 阿弥陀
User kusomushi
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 3440 Byte
Status AC
Exec Time 338 ms
Memory 52544 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 10 / 10 20 / 20 20 / 20 50 / 50
Status
AC × 9
AC × 18
AC × 18
AC × 29
Set Name Test Cases
Subtask1 sample_1.txt, 01_i.txt, 01_random01.txt, 01_random02.txt, 01_random03.txt, 01_random04.txt, 01_random05.txt, 01_random06.txt, 01_random07.txt
Subtask2 sample_1.txt, sample_2.txt, sample_3.txt, 02_i.txt, 02_p.txt, 02_random01.txt, 02_random02.txt, 02_random03.txt, 02_random04.txt, 02_random05.txt, 02_random06.txt, 02_random07.txt, 02_random08.txt, 02_rp01.txt, 02_rp02.txt, 02_rp03.txt, 02_rp04.txt, 02_rp05.txt
Subtask3 sample_1.txt, sample_2.txt, 03_i.txt, 03_random01.txt, 03_random02.txt, 03_random03.txt, 03_random04.txt, 03_random05.txt, 03_random06.txt, 03_random07.txt, 03_random08.txt, 03_random09.txt, 03_random10.txt, 03_random11.txt, 03_random12.txt, 03_random13.txt, 03_random14.txt, 03_random15.txt
Subtask4 sample_1.txt, sample_2.txt, sample_3.txt, 04_i.txt, 04_p1.txt, 04_p2.txt, 04_random01.txt, 04_random02.txt, 04_random03.txt, 04_random04.txt, 04_random05.txt, 04_random06.txt, 04_random07.txt, 04_random08.txt, 04_random09.txt, 04_random10.txt, 04_random11.txt, 04_random12.txt, 04_random13.txt, 04_rp01.txt, 04_rp02.txt, 04_rp03.txt, 04_rp04.txt, 04_rp05.txt, 04_rp06.txt, 04_rp07.txt, 04_rp08.txt, 04_rp09.txt, 04_rp10.txt
Case Name Status Exec Time Memory
01_i.txt AC 254 ms 42920 KB
01_random01.txt AC 71 ms 19156 KB
01_random02.txt AC 70 ms 23124 KB
01_random03.txt AC 70 ms 21332 KB
01_random04.txt AC 106 ms 23252 KB
01_random05.txt AC 198 ms 34180 KB
01_random06.txt AC 240 ms 41136 KB
01_random07.txt AC 260 ms 39720 KB
02_i.txt AC 94 ms 18004 KB
02_p.txt AC 79 ms 21844 KB
02_random01.txt AC 71 ms 21076 KB
02_random02.txt AC 71 ms 21076 KB
02_random03.txt AC 93 ms 21716 KB
02_random04.txt AC 77 ms 18004 KB
02_random05.txt AC 120 ms 22100 KB
02_random06.txt AC 153 ms 29140 KB
02_random07.txt AC 193 ms 42196 KB
02_random08.txt AC 184 ms 45744 KB
02_rp01.txt AC 91 ms 17876 KB
02_rp02.txt AC 92 ms 20436 KB
02_rp03.txt AC 91 ms 19668 KB
02_rp04.txt AC 82 ms 18388 KB
02_rp05.txt AC 81 ms 19412 KB
03_i.txt AC 70 ms 20052 KB
03_random01.txt AC 103 ms 21716 KB
03_random02.txt AC 163 ms 35960 KB
03_random03.txt AC 154 ms 30164 KB
03_random04.txt AC 156 ms 32368 KB
03_random05.txt AC 117 ms 21844 KB
03_random06.txt AC 105 ms 21972 KB
03_random07.txt AC 121 ms 22740 KB
03_random08.txt AC 80 ms 19796 KB
03_random09.txt AC 118 ms 26964 KB
03_random10.txt AC 146 ms 28756 KB
03_random11.txt AC 160 ms 35668 KB
03_random12.txt AC 157 ms 35548 KB
03_random13.txt AC 145 ms 31572 KB
03_random14.txt AC 156 ms 32412 KB
03_random15.txt AC 117 ms 22228 KB
04_i.txt AC 338 ms 48228 KB
04_p1.txt AC 284 ms 40600 KB
04_p2.txt AC 275 ms 45976 KB
04_random01.txt AC 236 ms 43184 KB
04_random02.txt AC 201 ms 34924 KB
04_random03.txt AC 182 ms 31388 KB
04_random04.txt AC 197 ms 42352 KB
04_random05.txt AC 208 ms 41520 KB
04_random06.txt AC 249 ms 47384 KB
04_random07.txt AC 247 ms 42688 KB
04_random08.txt AC 221 ms 35912 KB
04_random09.txt AC 226 ms 39336 KB
04_random10.txt AC 223 ms 40992 KB
04_random11.txt AC 318 ms 49352 KB
04_random12.txt AC 315 ms 50500 KB
04_random13.txt AC 317 ms 52544 KB
04_rp01.txt AC 283 ms 44500 KB
04_rp02.txt AC 274 ms 43136 KB
04_rp03.txt AC 282 ms 42124 KB
04_rp04.txt AC 301 ms 43552 KB
04_rp05.txt AC 282 ms 44784 KB
04_rp06.txt AC 275 ms 41504 KB
04_rp07.txt AC 277 ms 43172 KB
04_rp08.txt AC 304 ms 44900 KB
04_rp09.txt AC 284 ms 42120 KB
04_rp10.txt AC 287 ms 43156 KB
sample_1.txt AC 71 ms 20948 KB
sample_2.txt AC 71 ms 17364 KB
sample_3.txt AC 72 ms 18900 KB