Pagini recente » Cod sursa (job #1565044) | Cod sursa (job #1542263) | Cod sursa (job #1820125) | Cod sursa (job #694598) | Cod sursa (job #2814056)
#include <bits/stdc++.h>
using namespace std;
const int NRFII = 2,NMAX = 1e5,BITS = 20;
struct trie {
int poz;
trie *fii[NRFII];
trie() {
poz = 0;
for (int i = 0;i < NRFII;i++)
fii[i] = nullptr;
}
};
trie* t = new trie();
int s[NMAX + 5];
void update (trie* node, int val, int poz, int bit) {
if (bit == 0) {
node -> poz = poz;
return;
}
bool msb = (val & (1 << bit));
if (node -> fii[msb] == nullptr)
node -> fii[msb] = new trie();
update(node -> fii[msb], val, poz, bit - 1);
}
int query (trie* node, int val, int bit) {
if (bit == 0)
return node -> poz;
bool msb = (val & (1 << bit));
msb ^= 1;
if (node -> fii[msb] != nullptr)
return query(node -> fii[msb], val, bit - 1);
return query(node -> fii[(msb ^ 1)], val, bit - 1);
}
int main()
{
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n,x,a,pozi = 0,pozj = 0,mx = -1;
fin >> n;
update(t, 0, 0, BITS);
for (int i = 1;i <= n;i++) {
fin >> x;
s[i] = (s[i - 1] ^ x);
a = query(t, s[i], BITS);
if ((s[a] ^ s[i]) > mx) {
mx = (s[a] ^ s[i]);
pozi = a;
pozj = i;
}
update(t, s[i], i, BITS);
}
fout << mx << " " << pozi + 1 << " " << pozj;
return 0;
}