Pagini recente » Istoria paginii runda/simulareojicls11 | Istoria paginii runda/aabbbaaa/clasament | Cod sursa (job #2990151) | Istoria paginii runda/sdaf | Cod sursa (job #1537840)
#include <iostream>
#include <cstdio>
#define MAXN 100050
using namespace std;
struct nod
{
nod *next[2];
int ind;
nod(int _ind = -1)
{
next[0] = next[1] = NULL;
ind = _ind;
}
};
nod *root = new nod();
void insert(int x, int ind, nod *crt = root, int bitPos = 20)
{
if (bitPos < 0) {
if (crt->ind < ind)
crt->ind = ind;
return;
}
int bit = (x >> bitPos) & 1;
if (crt->next[bit] == NULL)
crt->next[bit] = new nod();
insert(x, ind, crt->next[bit], bitPos-1);
}
int xrs[MAXN]; /// xrs[i] = a1 xor a2 xor ... xor ai
int best, start, stop, n, x;
int searchBest(int x, int bitPos = 20, nod *crt = root)
{
if (bitPos < 0)
return crt->ind;
int bit = (x >> bitPos) & 1;
/// I want the opposite bit so a xor b --> 1
bit = !bit;
if (crt->next[bit] != NULL)
return searchBest(x, bitPos-1, crt->next[bit]);
else if (crt->next[!bit] != NULL)
return searchBest(x, bitPos-1, crt->next[!bit]);
else
cerr << "ERROR 50\n";
}
int main()
{
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
scanf("%d", &n);
insert(0, 0);
xrs[0] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
xrs[i] = xrs[i-1] ^ x;
int ind = searchBest(xrs[i]);
if (xrs[ind] ^ xrs[i] > best) {
best = xrs[ind] ^ xrs[i];
start = ind+1;
stop = i;
}
insert(xrs[i], i);
}
printf("%d %d %d", best, start, stop);
return 0;
}