// 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;
}
}
