Pagini recente » Cod sursa (job #2192959) | Cod sursa (job #1807200) | Cod sursa (job #33509) | Cod sursa (job #1917194) | Cod sursa (job #2730392)
#include <iostream>
#include <cstdio>
using namespace std;
const int LOGX = 20;
const int NMAX = 100000;
class nod {
public:
int dr;
bool viz;
nod() : dr(0), viz(false) {}
};
class trie {
private:
// nod noduri[100000];
nod noduri[(1 << (LOGX + 2)) + 100];
public:
void add_nr(int nr, int dr) {
int crt_idx = 0;
for(int p2 = 1 << LOGX; p2 > 0; p2 >>= 1) {
noduri[crt_idx].viz = true;
int bit = (nr & p2) == 0 ? 0 : 1;
crt_idx = (crt_idx << 1) + bit + 1;
}
noduri[crt_idx].viz = true;
noduri[crt_idx].dr = dr;
}
int get_xor_max(int nr, int &dr) {
int ret = 0;
int crt_idx = 0;
for(int p2 = 1 << LOGX; p2 > 0; p2 >>= 1) {
int best = ((nr & p2) ^ p2) == 0 ? 0 : 1;
if(!noduri[ (crt_idx << 1) + best + 1 ].viz)
best = 1 - best;
ret |= (p2 * best);
crt_idx = (crt_idx << 1) + best + 1;
}
dr = noduri[crt_idx].dr;
return ret;
}
};
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
int n, x, xor_prefix, xor_max, max_st, max_dr;
trie tr;
scanf("%d", &n);
xor_prefix = 0;
xor_max = -1;
for(int l = 1; l <= n; l++) {
tr.add_nr(xor_prefix, l - 1);
scanf("%d", &x);
xor_prefix ^= x;
int crt_dr;
int xor_crt = xor_prefix ^ tr.get_xor_max(xor_prefix, crt_dr); /// caut sufixul pt care xor_prefix ^ prefix este maxim
if(xor_crt > xor_max)
xor_max = xor_crt, max_st = crt_dr + 1, max_dr = l;
}
printf("%d %d %d", xor_max, max_st, max_dr);
return 0;
}