Pagini recente » Cod sursa (job #2810947) | Cod sursa (job #1515302) | Cod sursa (job #2248949) | Cod sursa (job #1845168) | Cod sursa (job #1878618)
#include <bits/stdc++.h>
#define NMax 100000
using namespace std;
struct trie{
int idx;
trie* leg[2];
void Init()
{
leg[0] = leg[1] = NULL;
}
};
trie *rad = new trie;
char s[24];
int sum[NMax+1];
int v[NMax+1];
int id;
void Insert(char* s)
{
int i,j;
trie *q, *p = rad;
for(i = 0; s[i]; ++i)
{
j = s[i]-'0';
if(!p->leg[j]){
q = new trie;
q->Init();
p->leg[j] = q;
}
p = p->leg[j];
}
p->idx = id;
}
int Search(char* s)
{
int i,j;
trie *p = rad;
for(i = 0; s[i]; ++i)
{
j = !(s[i]-'0');
if(p->leg[j]) p = p->leg[j];
else p = p->leg[!j];
}
return p->idx;
}
int main(){
FILE* fin = fopen("xormax.in","r");
FILE* fout = fopen("xormax.out","w");
int i,j,N,p,bit,res,inc,sf,vmax=0;
rad->Init();
fscanf(fin,"%d",&N);
for(i = 1; i <= N; ++i)
{
fscanf(fin,"%d",&v[i]);
vmax = max(vmax, v[i]);
}
for(bit = 20; bit && !(vmax & (1<<bit)); --bit);
for(i = 0; i <= bit; ++i) s[i] = '0';
Insert(s);
for(res = -1, i = 1; i <= N; ++i)
{
sum[i] = sum[i-1] ^ v[i];
for(j = bit; j >= 0; --j)
if(sum[i] & (1<<j)) s[bit-j] = '1';
else s[bit-j] = '0';
id = i;
Insert(s);
p = Search(s);
if((sum[i]^sum[p]) > res)
{
res = sum[i] ^ sum[p];
inc = p+1;
sf = i;
}
}
fprintf(fout,"%d %d %d\n",res,inc,sf);
return 0;
}