Submission #143451

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
143451	2019-08-14T05:26:00 Z	model_code	Data Transfer (IOI19_transfer)	Java 11	100 / 100	946 ms	130532 KB

transfer

// correct/1_log_1_n.java

import java.util.Arrays;

/**
 * Optimal solution
 * K = 1+log(N+1)
 * @author Kian Mirjalali
 *
 */
class transfer {
	
	private int rangeXorVec(int[] v, int begin, int end) {
		int s = 0;
		for (int i = begin; i < end; i++)
			s ^= v[i];
		return s;
	}

	private int bitMaskXorVec(int[] v, int N, int bitIndex) {
		int s = 0;
		for (int i = 0; i < N; i++)
			if ((((i + 1) >> bitIndex) & 1) == 1)
				s ^= v[i];
		return s;
	}

	private int getL(int N) {
		int L = 0;
		for (int i=N; i>0; i/=2)
			L++;
		return L;
	}
	
	private int callLimit(int N) {
		switch (N) {
		case 63:  return 20000;
		case 255: return 200000;
		}
		throw new Error("invalid value of N: "+N);
	}

	private static int callCount = 0;
	
	int[] get_attachment(int[] source) {
		final int N = source.length;
		if (++callCount > callLimit(N))
			throw new Error("too many calls of get_attachment() : "+callCount);
		int L = getL(N);
		int[] attachment = new int[L+1];
		int h = 0;
		for (int l=0; l<L; l++)
			attachment[h++] = bitMaskXorVec(source, N, l);
		attachment[h++]= rangeXorVec(attachment, 0, L);
		return attachment;
	}
	
	int[] retrieve(int[] data) {
		int ds = data.length;
		int N = ds/2;
		while (N+getL(N)+1 < ds)
			N++;
		if (++callCount > callLimit(N))
			throw new Error("too many calls of retrieve() : "+callCount);
		int[] result = Arrays.copyOfRange(data, 0, N);
		int[] attachment = Arrays.copyOfRange(data, N, data.length);
		int L = attachment.length-1;
		if (attachment[attachment.length-1] != rangeXorVec(attachment, 0, L))
			return result;
		int c = 0;
		for (int l=0; l<L; l++)
			if (attachment[l] != bitMaskXorVec(result, N, l))
				c |= (1<<l);
		c--;
		if (c >= 0)
			result[c] = 1-result[c];
		return result;

	}
	
}

Subtask #1

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	270 ms	25688 KB	Output is correct
2	Correct	266 ms	26500 KB	Output is correct
3	Correct	276 ms	26028 KB	Output is correct
4	Correct	255 ms	25676 KB	Output is correct
5	Correct	257 ms	25760 KB	Output is correct
6	Correct	265 ms	25992 KB	Output is correct
7	Correct	269 ms	25812 KB	Output is correct
8	Correct	269 ms	25828 KB	Output is correct
9	Correct	264 ms	25948 KB	Output is correct
10	Correct	266 ms	25872 KB	Output is correct
11	Correct	259 ms	25928 KB	Output is correct
12	Correct	268 ms	25764 KB	Output is correct
13	Correct	273 ms	25664 KB	Output is correct
14	Correct	260 ms	25876 KB	Output is correct
15	Correct	277 ms	25940 KB	Output is correct
16	Correct	274 ms	25888 KB	Output is correct
17	Correct	274 ms	26548 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	913 ms	129916 KB	Output is correct
2	Correct	894 ms	130212 KB	Output is correct
3	Correct	917 ms	129840 KB	Output is correct
4	Correct	913 ms	129788 KB	Output is correct
5	Correct	918 ms	130112 KB	Output is correct
6	Correct	891 ms	130252 KB	Output is correct
7	Correct	902 ms	129996 KB	Output is correct
8	Correct	897 ms	130184 KB	Output is correct
9	Correct	909 ms	129488 KB	Output is correct
10	Correct	903 ms	130108 KB	Output is correct
11	Correct	898 ms	130532 KB	Output is correct
12	Correct	929 ms	130016 KB	Output is correct
13	Correct	915 ms	128964 KB	Output is correct
14	Correct	914 ms	129980 KB	Output is correct
15	Correct	909 ms	129756 KB	Output is correct
16	Correct	936 ms	129896 KB	Output is correct
17	Correct	946 ms	130164 KB	Output is correct
18	Correct	907 ms	129560 KB	Output is correct
19	Correct	945 ms	130108 KB	Output is correct