Pagini recente » Cod sursa (job #1674225) | Cod sursa (job #1079748) | Cod sursa (job #224984) | Cod sursa (job #2663545) | Cod sursa (job #2918183)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
#define cin fin
#define cout fout
#define N 100005
int n, st, dr, a[N];
struct Trie
{
Trie *zero, *unu;
int poz;
};
Trie *trie = new Trie;
void adauga(int x, int ind)
{
Trie *p = trie;
for(int i = 22 ; i >= 0 ; i--)
{
if(((x>>i)&1) == 1)
{
if(p->unu == NULL)
{
p->unu = new Trie;
p->unu->zero = NULL;
p->unu->unu = NULL;
}
p = p->unu;
}
else
{
if(p->zero == NULL)
{
p->zero = new Trie;
p->zero->unu = NULL;
p->zero->zero = NULL;
}
p = p->zero;
}
}
p->poz = ind;
}
int fa(int a[])
{
adauga(0,0);
int maxim = 0;
int xr = 0;
for(int i = 1 ; i <= n ; i++)
{
xr ^= a[i];
Trie *p = trie;
int x = 0;
for(int j = 22 ; j >= 0 ; j--)
{
if(((xr>>j)&1) == 1)
{
if(p->zero == NULL)
{
x |= (1<<j);
p = p->unu;
}
else p = p->zero;
}
else
{
if(p->unu == NULL)
{
p = p->zero;
}
else
{
x |= (1<<j);
p = p->unu;
}
}
}
if((x^xr) > maxim)
{
maxim = x^xr;
dr = i;
st = p->poz;
}
adauga(xr,i);
}
return maxim;
}
int main() {
trie->unu = NULL;
trie->zero = NULL;
cin >> n;
for(int i = 1 ; i <= n ; i++)
{
cin >> a[i];
}
cout << fa(a) << " " << st+1 << " " << dr;
return 0;
}