Pagini recente » Cod sursa (job #1938993) | Cod sursa (job #3254420) | Cod sursa (job #1187504) | Cod sursa (job #1531232) | Cod sursa (job #2930625)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
struct trie{
int poz;
trie *son[2];
trie(){
poz = 0;
son[0] = son[1] = NULL;
}
};
trie *T = new trie;
int n , x , maxx , maxxi , maxxj , s = 0;
void Insert(trie *Nod , int i , int val , int curr){
if(curr < 0){
Nod -> poz = i;
return;
}
int p = (val & (1 << curr)) != 0;
if(Nod -> son[p] == NULL)
Nod -> son[p] = new trie;
Insert(Nod -> son[p] , i , val , curr - 1);
}
pi Find(trie *Nod , int ans , int val , int curr){
if(curr < 0)
return {ans , Nod->poz};
int p = (val & (1 << curr)) != 0;
p ^= 1;
if(Nod->son[p] == NULL)
p ^= 1;
return Find(Nod -> son[p] , ans + p * (1 << curr) , val , curr - 1);
}
int main()
{
freopen("xormax.in" , "r" , stdin);
freopen("xormax.out" , "w" , stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
Insert(T , 0 , 0 , 20);
for(int i = 1;i <= n; ++i){
cin >> x;
s ^= x;
auto t = Find(T , 0 , s , 20);
// cout << t.first << " " << t.second + 1 << " " << i << "\n";
if(t.first ^ s > maxx){
maxx = t.first ^ s;
maxxi = t.second + 1;
maxxj = i;
}
Insert(T , i , s , 20);
}
cout << maxx << " " << maxxi << " " << maxxj;
}