Pagini recente » Cod sursa (job #2879594) | Cod sursa (job #1335093) | Cod sursa (job #613406) | Cod sursa (job #766484) | Cod sursa (job #2965054)
#include <fstream>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int SIGMA = 2;
struct Trie
{
int pos;
Trie* children[SIGMA];
Trie()
{
pos = -1;
for(int i = 0; i < SIGMA; i++)
children[i] = NULL;
}
};
Trie* trie = new Trie();
void insert(Trie* root, int x, int pos, int bit = 21)
{
if(bit == -1)
{
root->pos = pos;
return;
}
int nxt = ((x & (1 << bit)) != 0);
if(root->children[nxt] == NULL)
root->children[nxt] = new Trie();
insert(root->children[nxt], x, pos, bit - 1);
}
pair<int, int> query(Trie* root, int x, int bit = 21, int ans = 0)
{
if(bit == -1)
return {ans, root->pos};
int nxt = ((x & (1 << bit)) == 0);
if(root->children[nxt] == NULL)
nxt = nxt ^ 1;
return query(root->children[nxt], x, bit - 1, ans + (1 << bit) * nxt);
}
int main()
{
int n, i, j, ans = -1, l, r, xr = 0, x;
cin >> n;
insert(trie, 0, 0);
for(i = 1; i <= n; i++)
{
cin >> x;
xr ^= x;
pair<int, int> p = query(trie, xr);
p.first ^= xr;
if(p.first > ans)
{
ans = p.first;
l = p.second + 1;
r = i;
}
insert(trie, xr, i);
}
cout << ans << ' ' << l << ' ' << r;
return 0;
}