Pagini recente » Cod sursa (job #2743054) | Cod sursa (job #1517368) | Cod sursa (job #2238337) | Cod sursa (job #488945) | Cod sursa (job #1960136)
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
const int NMax = 100001;
const int BitMax = 22;
struct Trie{
int sons[2];
};
Trie T[NMax * 2];
int Size = 0;
int n,mx,ind;
int a[NMax],x[NMax],v[NMax];
vector<int> e[NMax];
int main()
{
f >> n;
for(int i = 1; i <= n; ++i){
f >> a[i];
if(i == 1)
x[i] = a[i];
else
x[i] = x[i - 1] ^ a[i];
}
for(int i = 0; i <= n; ++i){
int aux = x[i],nr = 0;
while(aux){
v[++nr] = aux % 2;
aux /= 2;
}
while(nr < BitMax){
v[++nr] = 0;
}
///adaug in trie
int node = 0;
for(int j = nr; j >= 1; --j){
e[i].push_back(v[j]);
int next = T[node].sons[v[j]];
if(next == 0){
next = ++Size;
T[node].sons[v[j]] = next;
}
node = next;
}
node = 0;
int ans = 0;
for(int j = 0; j < e[i].size(); ++j){
if(T[node].sons[1 - e[i][j]]){
ans = ans * 2 + 1;
node = T[node].sons[1 - e[i][j]];
}else{
ans = ans * 2;
node = T[node].sons[e[i][j]];
}
}
if(ans > mx){
ind = i;
mx = ans;
}
}
g << mx << ' ';
for(int i = 1; i <= n; ++i){
if((x[i] ^ x[ind]) == mx){
g << i + 1 << ' ' << ind << '\n';
return 0;
}
}
return 0;
}