Pagini recente » Cod sursa (job #243888) | Cod sursa (job #789159) | Cod sursa (job #2726119) | Cod sursa (job #3254816) | Cod sursa (job #2661441)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n, aux;
struct date
{ int sol, pi, pf;
}ans, val, var;
struct Trie
{ int cnt;
Trie *fiu[2];
Trie()
{ fiu[0] = fiu[1] = 0;
cnt = 0;
}
};
Trie *T = new Trie;
void ins(Trie *nod, int x, int bit, int idx)
{ if(bit < 0)
{ nod->cnt = idx;
return;
}
aux = 0;
if(x & (1 << bit)) aux = 1;
if(!nod->fiu[aux])
nod->fiu[aux] = new Trie;
ins(nod->fiu[aux], x, bit-1, idx);
}
date query(Trie *nod, int x, int bit, int idx, int curr)
{ if(bit < 0)
{ var.sol = curr;
var.pi = nod->cnt + 1;
var.pf = idx;
return var;
}
aux = 0;
if(x & (1 << bit)) aux = 1;
if(nod->fiu[1-aux])
{ curr = (curr << 1) + 1;
return query(nod->fiu[1-aux], x, bit-1, idx, curr);
}
else
{ curr = (curr << 1);
return query(nod->fiu[aux], x, bit-1, idx, curr);
}
}
int main()
{
f >> n;
int xr = 0;
ans.sol = -1;
ins(T, 0, 20, 0);
for(int i=1; i<=n; i++)
{ int x;
f >> x;
xr = xr ^ x;
ins(T, xr, 20, i);
val = query(T, xr, 20, i, 0);
if(val.sol > ans.sol) ans = val;
}
if(ans.pi > ans.pf) ans.pi = ans.pf;
g << ans.sol << ' ' << ans.pi << ' ' << ans.pf << '\n';
return 0;
}