Pagini recente » Cod sursa (job #1085410) | Cod sursa (job #2243146) | Cod sursa (job #2871986) | Cod sursa (job #93110) | Cod sursa (job #2661422)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n;
pair <int, pair <int, int> > ans, val;
struct Trie
{ int nrfii, cnt;
Trie *fiu[3];
Trie()
{ fiu[0] = fiu[1] = 0;
nrfii = cnt = 0;
}
};
Trie *T = new Trie;
void ins(Trie *nod, int x, int bit, int idx)
{ if(bit < 0)
{ nod->cnt = idx;
return;
}
int val = 0;
if(x & (1 << bit)) val = 1;
if(!nod->fiu[val])
{ nod->fiu[val] = new Trie;
nod->nrfii++;
}
ins(nod->fiu[val], x, bit-1, idx);
}
pair <int, pair <int, int> > query(Trie *nod, int x, int bit, int idx, int curr)
{ if(bit < 0) return {curr, {nod->cnt, idx}};
int val = 0;
if(x & (1 << bit)) val = 1;
if(nod->fiu[1-val])
{ curr = (curr << 1) + 1;
return query(nod->fiu[1-val], x, bit-1, idx, curr);
}
else
{ curr = (curr << 1);
return query(nod->fiu[val], x, bit-1, idx, curr);
}
}
int main()
{
f >> n;
int xr = 0;
ans.first = -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.first > ans.first) ans = val;
}
g << ans.first << ' ' << min(ans.second.first + 1, ans.second.second) << ' ' << ans.second.second << '\n';
return 0;
}