Pagini recente » Cod sursa (job #1422489) | Cod sursa (job #1438455) | Cod sursa (job #2100250) | Cod sursa (job #3033599) | Cod sursa (job #2289429)
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trie {
int poz;
trie *son[2];
trie() {
son[1] = son[0] = 0;
}
};
trie *t = new trie();
const int nMax = 100000;
int n, xori[nMax + 5], solx, soly, maxim = -1;
void Add(trie *nod, int poz) {
trie *fiu = nod;
for (int i = 22; i >= 0; i--) {
int k = ((xori[poz] & (1 << i)) > 0);
if (fiu -> son[k] == 0)
fiu -> son[k] = new trie();
fiu = fiu -> son[k];
}
fiu -> poz = poz;
}
int Find(trie *nod, int nr) {
trie *fiu = nod;
for (int i = 22; i >= 0; i--) {
int k = ((nr & (1 << i)) > 0) ;
if (fiu -> son[k ^ 1] == 0)
fiu = fiu -> son[k];
else
fiu = fiu -> son[k ^ 1];
}
return fiu -> poz;
}
int main() {
fin >> n;
Add(t, 0);
for (int i = 1; i <= n; i++) {
int nr;
fin >> nr;
xori[i] = xori[i-1] ^ nr;
int poz = Find(t, xori[i]);
if ((xori[i] ^ xori[poz]) > maxim) {
maxim = xori[i] ^ xori[poz];
solx = poz;
soly = i;
}
Add(t, i);
}
fout << maxim << " " << solx + 1 << " " << soly << '\n';
}