Pagini recente » Cod sursa (job #1905448) | Cod sursa (job #1058610) | Cod sursa (job #482020) | Cod sursa (job #2890974) | Cod sursa (job #2533824)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
struct trie{
trie *f[2];
int poz;
trie(){
f[0] = f[1] = 0;
poz = 0;
}
};
int st, dr, sol, n, maxim, x, nr, pozs;
int s[100005];
trie *rad;
void insereaza (trie *rad, int bit, int val, int poz) {
if (bit == -1) {
rad->poz = poz;
return;
}
if ( ( (val >> bit) & 1 ) == 0) {
if (rad->f[0] == NULL)
rad->f[0] = new trie();
insereaza (rad->f[0], bit-1, val, poz);
}
else {
if (rad->f[1] == NULL)
rad->f[1] = new trie();
insereaza (rad->f[1], bit-1, val, poz);
}
}
void cautare (trie *rad, int bit, int val) {
if (bit == -1) {
pozs = rad->poz;
return;
}
int beat = ( (val >> bit) & 1 );
if (rad->f[1-beat] != 0) {
cautare (rad->f[1-beat], bit-1, val);
}
else {
cautare (rad->f[beat], bit-1, val);
}
}
int main(){
fin >> n;
sol = -1;
for (int i=1; i<=n; i++){
fin >> x;
if (i == 1) {
s[i] = x;
}
else{
s[i] = (x ^ s[i-1]);
maxim = max (maxim, x);
}
}
while (maxim){
nr++;
maxim /= 2;
}
rad = new trie();
insereaza (rad, nr, 0, 0);
for (int i=1; i<=n; i++){
cautare (rad, nr, s[i]);
if ((s[pozs] ^ s[i]) > sol){
sol = (s[pozs] ^ s[i]);
st = pozs + 1, dr = i;
}
insereaza (rad, nr, s[i], i);
}
fout << sol << " " << st << " " << dr;
return 0;
}