Pagini recente » Cod sursa (job #1917948) | Cod sursa (job #1327508) | Istoria paginii runda/noaptea_burlacilor/clasament | Istoria paginii runda/oni_2016_10-ziua2/clasament | Cod sursa (job #2968728)
#include <bits/stdc++.h>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
int n, a, x, poz1,poz2,afs, afs1, poz1_f, poz2_f;
struct TrieNode {
int frg;
TrieNode *nxt[2];
TrieNode() {
frg = -1;
for (int i = 0; i < 2; i++) {
nxt[i] = NULL;
}
}
};
TrieNode * root = new TrieNode;
void add(TrieNode * root, int N,int pos) {
TrieNode *curr = root;
for(int bit = 20; bit >= 0; bit--) {
bool now = (N & (1 << bit));
if(curr -> nxt[now] == NULL) {
curr -> nxt[now] = new TrieNode;
}
curr = curr -> nxt[now];
}
curr -> frg = pos;
}
void lookup(TrieNode * root, int N, int pos) {
TrieNode *curr = root;
afs1 = 0;
for(int bit = 20; bit >= 0; bit--) {
int now = (N & (1 << bit));
now = now >> bit;
if (curr == NULL) {
return;
}
if(curr -> nxt[!now] == NULL) {;
curr = curr -> nxt[now];
} else {
curr = curr -> nxt[!now];
afs1 |= (1 << bit);
}
/*
if (curr -> nxt[now] == NULL) {
now = now ^ 1;
}
afs1 = afs1 + (1 << bit) * now;
curr = curr -> nxt[now];
*/
}
poz1 = curr -> frg;
}
int main () {
in >> n;
add(root, 0, 0);
afs = -1;
for(int i = 1; i <= n; i++) {
in >> a;
x = x ^ a;
lookup(root,x,i);
if (afs < afs1) {
afs = afs1;
poz1_f = poz1 + 1;
poz2_f = i;
}
add(root,x,i);
}
out << afs << ' ' << poz1_f << ' ' << poz2_f;
return 0;
}