Pagini recente » Cod sursa (job #1481740) | Cod sursa (job #2420742) | Cod sursa (job #2038932) | Cod sursa (job #73919) | Cod sursa (job #2473536)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int nmax = 100000, lgmax = 20;
struct Trie{
int ind;
Trie *son[2];
Trie(){
memset(son, 0, sizeof son);
ind = 0;
}
};
Trie *trie = new Trie;
int n, v[nmax + 5], smax, l, r;
void Read(){
fin >> n;
for (int i = 1; i <= n; i++){
fin >> v[i];
v[i] ^= v[i - 1];
}
}
void Insert(int ind, int pos, Trie *p){
if (pos == 0){
p->ind = ind;
return;
}
bool x = (1 << pos) & v[ind];
if (!p->son[x])
p->son[x] = new Trie;
Insert(ind, pos - 1, p->son[x]);
}
int Search(int ind, int pos, Trie *p){
if (pos == 0)
return p->ind;
bool x = (1 << pos) & v[ind];
if (p->son[1 - x])
return Search(ind, pos - 1, p->son[1 - x]);
else
return Search(ind, pos - 1, p->son[x]);
}
void Solve(){
Insert(0, lgmax, trie);
l = r = 1;
for (int i = 1; i <= n; i++){
int index = Search(i, lgmax, trie);
int sum = v[i] ^ v[index];
if (sum > smax){
smax = sum;
l = index + 1;
r = i;
}
Insert(i, lgmax, trie);
}
fout << smax << ' ' << l << ' ' << r << '\n';
}
int main(){
Read();
Solve();
return 0;
}