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 |
|
|
|
|
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 |