제출 #143451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143451		model_code	Data Transfer (IOI19_transfer)	Java	100 / 100	946 ms	130532 KiB

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 / 60
• Subtask 2: 40 / 40