Pagini recente » Cod sursa (job #1289508) | Cod sursa (job #1808730) | Cod sursa (job #286919) | Cod sursa (job #1296575) | Cod sursa (job #1464769)
# include <bits/stdc++.h>
using namespace std;
ifstream fi("xormax.in");
ofstream fo("xormax.out");
struct trie{
trie * a[2];
trie () { a[0] = a[1] = NULL; }
};
trie * root = new trie();
void ins(int x)
{
trie * p = new trie();
p = root;
for (int i=21;i>=0;i--){
int bit= (1<<i) & x; bit = bit != 0;
if (!p->a[bit]) p->a[bit] = new trie();
p = p->a[bit];
}
}
int query(int x)
{
trie * p = new trie();
p = root;
int ret = 0;
for (int i=21;i>=0;i--){
int bit = (1<<i) & x; bit = (bit != 0);
bit ^= 1;
if (p->a[bit]) ret=ret*2+1;
else ret*=2, bit^=1;
p = p->a[bit];
}
return ret;
}
int n, a[100004], x[100004], res, stop, start;
int main()
{
fi>>n;
for (int i=1;i<=n;i++)
{
fi >> a[i];
x[i] = a[i];
if (i == 1)
{
ins(x[i]); res=max(res,x[i]);
continue;
}
x[i] ^= x[i-1];
int can = query(x[i]);
if (can > res)
{
res = can;
stop = i;
}
ins(x[i]);
}
int sum = a[stop];
int i;
for ( i=stop-1; sum != res; i--) sum ^= a[i];
start = i+1;
fo << res << " " << start << " " << stop;
return 0;
}