Pagini recente » Cod sursa (job #2517373) | Cod sursa (job #1739697) | Cod sursa (job #633225) | Cod sursa (job #1462108) | Cod sursa (job #2400225)
#include <cstdio>
#include <cstring>
using namespace std;
int v[(1<<24) - 1];
int main()
{
FILE *fin=fopen ("xormax.in","r");
FILE *fout=fopen ("xormax.out","w");
int n,sol,inc,sf,x,bit,poz,val,i,nr,solc;
fscanf (fin,"%d",&n);
nr=0;
sf=1000000000;
inc=0;
memset (v,-1,sizeof(v));
sol=-1;
bit = 23;
poz=1;
v[poz] = 0;
solc=0;
while (bit>0){
val = 0;
/// val e valoarea de pe pozitia bit a lui nr
v[2*poz] = 0;
poz = 2*poz;
bit --;
}
for (i=1;i<=n;i++){
fscanf (fin,"%d",&x);
nr = (x ^ nr);
/// pasul 1 : cauti opusul lui nr in trie
bit = 23;
poz=1;
solc=0;
while (bit>0){
val = (nr & (1<<(bit-1)));
if (val!=0)
val = 1;
/// val e valoarea de pe pozitia bit a lui nr
val = 1-val;
if (val==0){
if (v[2*poz] != -1){ /// exista
solc = solc + (1<<(bit-1));
poz=2*poz;
}
else poz=2*poz+1;
}
else if (val==1){
if (v[2*poz+1] != -1){ /// exista
solc = solc + (1<<(bit-1));
poz=2*poz+1;
}
else poz=2*poz;
}
bit --;
}
if (solc > sol || (solc==sol && i-v[poz] < sf-inc)){
inc = v[poz];
sf = i;
sol= solc;
}
/// pasul 2 : update trie
bit = 23;
poz=1;
solc=0;
while (bit>0){
val = (nr & (1<<(bit-1)));
if (val!=0)
val = 1;
/// val e valoarea de pe pozitia bit a lui nr
if (val==0){
v[2*poz] = 0;
poz = 2*poz;
}
else if (val==1){
v[2*poz+1] = 0;
poz = 2*poz+1;
}
bit --;
}
v[poz] = i;
}
fprintf (fout,"%d %d %d",sol,inc+1,sf);
return 0;
}