Pagini recente » Cod sursa (job #2026495) | Cod sursa (job #1003943) | Cod sursa (job #2296452) | Cod sursa (job #3330114) | Cod sursa (job #3352515)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXB = 21; // 0..20 bits
struct Trie {
struct Node {
int nxt[2];
int idx;
Node() {
nxt[0] = nxt[1] = 0;
idx = -1;
}
} t[MAXN * MAXB + 5];
int len = 1;
void add(int x, int idx) {
int u = 1;
for(int i = MAXB - 1; i >= 0; i--) {
int bit = (x >> i) & 1;
if(!t[u].nxt[bit])
t[u].nxt[bit] = ++len;
u = t[u].nxt[bit];
}
t[u].idx = idx;
}
pair<int,int> findbest(int x) {
int u = 1;
int ans = 0;
for(int i = MAXB - 1; i >= 0; i--) {
int bit = (x >> i) & 1;
if(t[u].nxt[1 - bit]) {
ans |= (1 << i);
u = t[u].nxt[1 - bit];
} else {
u = t[u].nxt[bit];
}
}
return {ans, t[u].idx};
}
} trie;
int main() {
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n;
cin >> n;
int x, xorr = 0;
int ans = 0, l = 1, r = 1;
// IMPORTANT: prefix XOR = 0 la poziția 0
trie.add(0, 0);
for(int i = 1; i <= n; i++) {
cin >> x;
xorr ^= x;
auto best = trie.findbest(xorr);
if(best.first > ans) {
ans = best.first;
l = best.second + 1;
r = i;
}
trie.add(xorr, i);
}
cout << ans << " " << l << " " << r << "\n";
return 0;
}