Pagini recente » Cod sursa (job #1096234) | Cod sursa (job #2633903) | Borderou de evaluare (job #2014795) | Cod sursa (job #2720313) | Cod sursa (job #765658)
Cod sursa(job #765658)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 100001
#define ln printf("\n")
int a[MAX],sum[MAX],n;
struct trie{
struct trie *f[2];
int idx; }*t;
void adauga(int x,int idx){
trie *g = t;
int urm;
for(int i=20;i>=0;i--)
{
if(x & (1<<i))urm = 1; else urm = 0;
if(g->f[urm] == 0)g->f[urm] = new trie;
g = g->f[urm];
}
g->idx = idx; // setam pozitia in care am gasit suma respectiva
}
int search(int x){
trie *g = t;
int urm;
for(int i=20;i>=0;i--)
{
if(x & (1<<i))urm = 0; else urm = 1; // opusul bitului
if(g->f[urm]) g = g->f[urm]; else g = g->f[(!urm)];
}
return g->idx;
}
void rezolva(){
t = new trie;
int best = a[1], l_idx = 1 ,r_idx = 1, p;
for(int i=1;i<=n;i++)
{
sum[i] = sum[i-1] ^ a[i];
adauga(sum[i],i); // adaugam suma respectiva in trie cu pozitia i
p = search(sum[i]); // cautam valoarea optima
if( (sum[i] ^ sum[p]) > best )
{
best = sum[i] ^ sum[p];
l_idx = p + 1;
r_idx = i;
}
}
printf("%d %d %d\n",best,l_idx,r_idx);
}
/*
void rezolva(){
for(int i=1;i<=n;i++)sum[i] = sum[i-1] ^ a[i];
int best = -1, l_idx, r_idx, x;
for(int i=1;i<=n;i++)
{
for(int j=i;j>0;j--)
{
x = sum[j-1] ^ sum[i];
if(x > best)
{
best = x;
l_idx = j;
r_idx = i;
}
}
}
printf("%d %d %d\n",best,l_idx,r_idx);
}*/
int main(){
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
rezolva();
return 0;
}