oj.uz

답안 #143451

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143451 2019-08-14T05:26:00 Z model_code Data Transfer (IOI19_transfer) Java 11
100 / 100
 946 ms 130532 KB 
// 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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