Submission #214067


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[] st = new int[n];
			boolean[] vis = new boolean[n];
			for(int i = 0; i < n; i++) {
				if(vis[i]) continue;
				int j = p[i], k = 1;
				st[0] = i;
				for(; j != i; j = p[j]) st[k++] = j;
				for(int l = 0; l < k; l++, j = p[j]) {
					ans[j] = st[(d + l) % k];
					vis[j] = true;
				}
			}
			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 100
Code Size 8225 Byte
Status AC
Exec Time 932 ms
Memory 36312 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 751 ms 35692 KB
01_random01.txt AC 399 ms 20792 KB
01_random02.txt AC 389 ms 20788 KB
01_random03.txt AC 385 ms 20784 KB
01_random04.txt AC 466 ms 23400 KB
01_random05.txt AC 684 ms 35856 KB
01_random06.txt AC 648 ms 36000 KB
01_random07.txt AC 863 ms 35828 KB
02_i.txt AC 443 ms 20916 KB
02_p.txt AC 496 ms 20784 KB
02_random01.txt AC 562 ms 20660 KB
02_random02.txt AC 473 ms 20656 KB
02_random03.txt AC 517 ms 21740 KB
02_random04.txt AC 637 ms 20804 KB
02_random05.txt AC 498 ms 23936 KB
02_random06.txt AC 574 ms 24040 KB
02_random07.txt AC 551 ms 24232 KB
02_random08.txt AC 488 ms 24476 KB
02_rp01.txt AC 399 ms 20916 KB
02_rp02.txt AC 451 ms 20788 KB
02_rp03.txt AC 418 ms 20780 KB
02_rp04.txt AC 436 ms 20788 KB
02_rp05.txt AC 391 ms 20792 KB
03_i.txt AC 577 ms 20660 KB
03_random01.txt AC 463 ms 22508 KB
03_random02.txt AC 521 ms 23632 KB
03_random03.txt AC 514 ms 23688 KB
03_random04.txt AC 485 ms 23768 KB
03_random05.txt AC 541 ms 23948 KB
03_random06.txt AC 496 ms 23348 KB
03_random07.txt AC 589 ms 23744 KB
03_random08.txt AC 387 ms 20788 KB
03_random09.txt AC 497 ms 23860 KB
03_random10.txt AC 485 ms 23684 KB
03_random11.txt AC 520 ms 23844 KB
03_random12.txt AC 531 ms 23772 KB
03_random13.txt AC 572 ms 23688 KB
03_random14.txt AC 456 ms 23500 KB
03_random15.txt AC 464 ms 23348 KB
04_i.txt AC 694 ms 36240 KB
04_p1.txt AC 902 ms 35988 KB
04_p2.txt AC 775 ms 32316 KB
04_random01.txt AC 765 ms 30360 KB
04_random02.txt AC 636 ms 29640 KB
04_random03.txt AC 616 ms 25332 KB
04_random04.txt AC 551 ms 25612 KB
04_random05.txt AC 707 ms 25928 KB
04_random06.txt AC 666 ms 31396 KB
04_random07.txt AC 651 ms 29832 KB
04_random08.txt AC 678 ms 28660 KB
04_random09.txt AC 689 ms 27736 KB
04_random10.txt AC 785 ms 30708 KB
04_random11.txt AC 669 ms 35724 KB
04_random12.txt AC 726 ms 34568 KB
04_random13.txt AC 860 ms 35752 KB
04_rp01.txt AC 716 ms 35652 KB
04_rp02.txt AC 641 ms 36160 KB
04_rp03.txt AC 932 ms 35728 KB
04_rp04.txt AC 647 ms 36312 KB
04_rp05.txt AC 802 ms 35828 KB
04_rp06.txt AC 719 ms 35524 KB
04_rp07.txt AC 748 ms 35220 KB
04_rp08.txt AC 643 ms 36128 KB
04_rp09.txt AC 780 ms 36036 KB
04_rp10.txt AC 647 ms 35852 KB
sample_1.txt AC 497 ms 20784 KB
sample_2.txt AC 464 ms 20788 KB
sample_3.txt AC 384 ms 20784 KB