Submission #213988


Source Code Expand

Copy
import java.io.*;
import java.math.*;
import java.util.*;

import static java.util.Arrays.*;

public class Main {
	private static final int mod = (int)1e9+7;

	final Random random = new Random(0);
	final IOFast io = new IOFast();

	/// MAIN CODE
	public void run() throws IOException {
//		int TEST_CASE = Integer.parseInt(new String(io.nextLine()).trim());
		int TEST_CASE = 1;
		while(TEST_CASE-- != 0) {
			int n = io.nextInt();
			int m = io.nextInt();
			int d = io.nextInt();
			int[] ip = new int[n];
			int[] p = new int[n];
			for(int i = 0; i < n; i++) {
				ip[i] = i;
			}
			for(int i = 0; i < m; i++) {
				int j = io.nextInt() - 1;
				swap(ip, j, j + 1);
			}
			for(int i = 0; i < n; i++) {
				p[ip[i]] = i;
			}
//			System.err.println(Arrays.toString(p));

			int[] ans = new int[n];
			int[] ans2 = new int[n];
			int[] p100 = new int[n];
			for(int i = 0; i < n; i++) {
				ans[i] = i;
				int pos = i;
				for(int j = 0; j < 100; j++) {
					pos = p[pos];
				}
				p100[i] = pos;
			}
			
			for(int i = d - 1; i >= 0; ) {
				int[] perm;
				if(i >= 100) {
					i -= 100;
					perm = p100;
				}
				else {
					i--;
					perm = p;
				}
				for(int j = 0; j < n; j++) {
					ans2[j] = perm[ans[j]];
				}
				int[] t = ans;
				ans = ans2;
				ans2 = t;
			}
			for(int i = 0; i < n; i++) {
				io.out.println(++ans[i]);
			}
		}
	}
	

	/// TEMPLATE
	static int gcd(int n, int r) { return r == 0 ? n : gcd(r, n%r); }
	static long gcd(long n, long r) { return r == 0 ? n : gcd(r, n%r); }
	
	static <T> void swap(T[] x, int i, int j) {
		T t = x[i];
		x[i] = x[j];
		x[j] = t;
	}
	
	static void swap(int[] x, int i, int j) {
		int t = x[i];
		x[i] = x[j];
		x[j] = t;
	}
	

	static void radixSort(int[] xs) {
		int[] cnt = new int[(1<<16)+1];
		int[] ys = new int[xs.length];
		
		for(int j = 0; j <= 16; j += 16) {
			Arrays.fill(cnt, 0);
			for(int x : xs) { cnt[(x>>j&0xFFFF)+1]++; }
			for(int i = 1; i < cnt.length; i++) { cnt[i] += cnt[i-1]; }
			for(int x : xs) { ys[cnt[x>>j&0xFFFF]++] = x; }
			{ final int[] t = xs; xs = ys; ys = t; }
		}
	}
	
	static void radixSort(long[] xs) {
		int[] cnt = new int[(1<<16)+1];
		long[] ys = new long[xs.length];
		
		for(int j = 0; j <= 48; j += 16) {
			Arrays.fill(cnt, 0);
			for(long x : xs) { cnt[(int)(x>>j&0xFFFF)+1]++; }
			for(int i = 1; i < cnt.length; i++) { cnt[i] += cnt[i-1]; }
			for(long x : xs) { ys[cnt[(int)(x>>j&0xFFFF)]++] = x; }
			{ final long[] t = xs; xs = ys; ys = t; }
		}
	}
	

	static void arrayIntSort(int[][] x, int... keys) {
		Arrays.sort(x, new ArrayIntsComparator(keys));
	}
	
	static class ArrayIntsComparator implements Comparator<int[]> {
		final int[] KEY;
		
		public ArrayIntsComparator(int... key) {
			KEY = key;
		}
		
		@Override
		public int compare(int[] o1, int[] o2) {
			for(int k : KEY) if(o1[k] != o2[k]) return o1[k] - o2[k];
			return 0;
		}
	}
	
	static class ArrayIntComparator implements Comparator<int[]> {
		final int KEY;
		
		public ArrayIntComparator(int key) {
			KEY = key;
		}
		
		@Override
		public int compare(int[] o1, int[] o2) {
			return o1[KEY] - o2[KEY];
		}
	}
	
	
	void main() throws IOException {
		//		IOFast.setFileIO("rle-size.in", "rle-size.out");
		try {
			run();
		}
		catch (EndOfFileRuntimeException e) { }
		io.out.flush();
	}

	public static void main(String[] args) throws IOException {
		new Main().main();
	}
	
	static class EndOfFileRuntimeException extends RuntimeException {
		private static final long serialVersionUID = -8565341110209207657L; }

	static
	public class IOFast {
		private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		private PrintWriter out = new PrintWriter(System.out);

		void setFileIO(String ins, String outs) throws IOException {
			out.flush();
			out.close();
			in.close();
			in = new BufferedReader(new FileReader(ins));
			out = new PrintWriter(new FileWriter(outs));
			System.err.println("reading from " + ins);
		}

		//		private static final int BUFFER_SIZE = 50 * 200000;
		private static int pos, readLen;
		private static final char[] buffer = new char[1024 * 8];
		private static char[] str = new char[500*8*2];
		private static boolean[] isDigit = new boolean[256];
		private static boolean[] isSpace = new boolean[256];
		private static boolean[] isLineSep = new boolean[256];

		static {
			for(int i = 0; i < 10; i++) { isDigit['0' + i] = true; }
			isDigit['-'] = true;
			isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
			isLineSep['\r'] = isLineSep['\n'] = true;
		}

		public int read() throws IOException {
			if(pos >= readLen) {
				pos = 0;
				readLen = in.read(buffer);
				if(readLen <= 0) { throw new EndOfFileRuntimeException(); }
			}
			return buffer[pos++];
		}

		public int nextInt() throws IOException {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isSpace);
			
			int i = 0;
			int ret = 0;
			if(str[0] == '-') { i = 1; }
			for(; i < len; i++) ret = ret * 10 + str[i] - '0';
			if(str[0] == '-') { ret = -ret; }
			return ret;
//			return Integer.parseInt(nextString());
		}

		public long nextLong() throws IOException {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isSpace);
			
			int i = 0;
			long ret = 0;
			if(str[0] == '-') { i = 1; }
			for(; i < len; i++) ret = ret * 10 + str[i] - '0';
			if(str[0] == '-') { ret = -ret; }
			return ret;
//			return Long.parseLong(nextString());
		}

		public char nextChar() throws IOException {
			while(true) {
				final int c = read();
				if(!isSpace[c]) { return (char)c; }
			}
		}
		
		int reads(int len, boolean[] accept) throws IOException {
			try {
				while(true) {
					final int c = read();
					if(accept[c]) { break; }
					
					if(str.length == len) {
						char[] rep = new char[str.length * 3 / 2];
						System.arraycopy(str, 0, rep, 0, str.length);
						str = rep;
					}
					
					str[len++] = (char)c;
				}
			}
			catch(EndOfFileRuntimeException e) { ; }
			
			return len;
		}
		
		int reads(char[] cs, int len, boolean[] accept) throws IOException {
			try {
				while(true) {
					final int c = read();
					if(accept[c]) { break; }
					cs[len++] = (char)c;
				}
			}
			catch(EndOfFileRuntimeException e) { ; }
			
			return len;
		}

		public char[] nextLine() throws IOException {
			int len = 0;
			str[len++] = nextChar();
//			str[len++] = (char)read();
			len = reads(len, isLineSep);
			
			try {
				if(str[len-1] == '\r') { len--; read(); }
			}
			catch(EndOfFileRuntimeException e) { ; }
			
			return Arrays.copyOf(str, len);
		}

		public String nextString() throws IOException {
			return new String(next());
		}

		public char[] next() throws IOException {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isSpace);
			return Arrays.copyOf(str, len);
		}

		public int next(char[] cs) throws IOException {
			int len = 0;
			cs[len++] = nextChar();
			len = reads(cs, len, isSpace);
			return len;
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(nextString());
		}

		public long[] nextLongArray(final int n) throws IOException {
			final long[] res = new long[n];
			for(int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public int[] nextIntArray(final int n) throws IOException {
			final int[] res = new int[n];
			for(int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public int[][] nextIntArray2D(final int n, final int k) throws IOException {
			final int[][] res = new int[n][];
			for(int i = 0; i < n; i++) {
				res[i] = nextIntArray(k);
			}
			return res;
		}

		public int[][] nextIntArray2DWithIndex(final int n, final int k) throws IOException {
			final int[][] res = new int[n][k+1];
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < k; j++) {
					res[i][j] = nextInt();
				}
				res[i][k] = i;
			}
			return res;
		}

		public double[] nextDoubleArray(final int n) throws IOException {
			final double[] res = new double[n];
			for(int i = 0; i < n; i++) {
				res[i] = nextDouble();
			}
			return res;
		}

	}

}

Submission Info

Submission Time
Task D - 阿弥陀
User tanzaku
Language Java (OpenJDK 1.7.0)
Score 50
Code Size 8413 Byte
Status TLE
Exec Time 4058 ms
Memory 35384 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 10 / 10 20 / 20 20 / 20 0 / 50
Status
AC × 9
AC × 18
AC × 18
AC × 3
TLE × 26
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 995 ms 34752 KB
01_random01.txt AC 497 ms 20784 KB
01_random02.txt AC 460 ms 20776 KB
01_random03.txt AC 470 ms 20648 KB
01_random04.txt AC 457 ms 23516 KB
01_random05.txt AC 733 ms 35124 KB
01_random06.txt AC 871 ms 35000 KB
01_random07.txt AC 769 ms 35384 KB
02_i.txt AC 413 ms 21624 KB
02_p.txt AC 457 ms 21684 KB
02_random01.txt AC 414 ms 20780 KB
02_random02.txt AC 419 ms 20784 KB
02_random03.txt AC 491 ms 22832 KB
02_random04.txt AC 548 ms 21684 KB
02_random05.txt AC 491 ms 24076 KB
02_random06.txt AC 598 ms 23796 KB
02_random07.txt AC 619 ms 24408 KB
02_random08.txt AC 613 ms 23580 KB
02_rp01.txt AC 509 ms 21068 KB
02_rp02.txt AC 433 ms 21164 KB
02_rp03.txt AC 527 ms 21436 KB
02_rp04.txt AC 466 ms 21288 KB
02_rp05.txt AC 456 ms 21556 KB
03_i.txt AC 732 ms 23504 KB
03_random01.txt AC 557 ms 24544 KB
03_random02.txt AC 567 ms 25200 KB
03_random03.txt AC 922 ms 25556 KB
03_random04.txt AC 825 ms 25088 KB
03_random05.txt AC 851 ms 24340 KB
03_random06.txt AC 911 ms 25572 KB
03_random07.txt AC 801 ms 24276 KB
03_random08.txt AC 748 ms 23500 KB
03_random09.txt AC 828 ms 25032 KB
03_random10.txt AC 876 ms 25340 KB
03_random11.txt AC 837 ms 25068 KB
03_random12.txt AC 766 ms 25000 KB
03_random13.txt AC 857 ms 25544 KB
03_random14.txt AC 637 ms 25284 KB
03_random15.txt AC 822 ms 24444 KB
04_i.txt TLE 4036 ms 28880 KB
04_p1.txt TLE 4051 ms 29184 KB
04_p2.txt TLE 4035 ms 28232 KB
04_random01.txt TLE 4041 ms 27940 KB
04_random02.txt TLE 4038 ms 28116 KB
04_random03.txt TLE 4041 ms 25104 KB
04_random04.txt TLE 4041 ms 25268 KB
04_random05.txt TLE 4037 ms 25212 KB
04_random06.txt TLE 4037 ms 28432 KB
04_random07.txt TLE 4058 ms 27680 KB
04_random08.txt TLE 4038 ms 27600 KB
04_random09.txt TLE 4036 ms 27724 KB
04_random10.txt TLE 4036 ms 28124 KB
04_random11.txt TLE 4055 ms 28952 KB
04_random12.txt TLE 4037 ms 28728 KB
04_random13.txt TLE 4037 ms 29120 KB
04_rp01.txt TLE 4056 ms 28672 KB
04_rp02.txt TLE 4036 ms 28568 KB
04_rp03.txt TLE 4038 ms 28684 KB
04_rp04.txt TLE 4036 ms 28504 KB
04_rp05.txt TLE 4048 ms 29088 KB
04_rp06.txt TLE 4036 ms 28880 KB
04_rp07.txt TLE 4041 ms 28840 KB
04_rp08.txt TLE 4036 ms 29176 KB
04_rp09.txt TLE 4037 ms 29080 KB
04_rp10.txt TLE 4038 ms 29064 KB
sample_1.txt AC 590 ms 20784 KB
sample_2.txt AC 492 ms 20788 KB
sample_3.txt AC 437 ms 20752 KB