Pagini recente » Cod sursa (job #2377764) | Cod sursa (job #1220882) | Cod sursa (job #933350) | Cod sursa (job #1578899) | Cod sursa (job #3189409)
#include <bits/stdc++.h>
using namespace std;
#define INFILE "xormax.in"
#define OUTFILE "xormax.out"
const int BIT_MAX = 20;
const int N_MAX = 1e5 + 5;
struct Trie {
int ind;
Trie *children[2];
Trie() : ind(0){
children[0] = children[1] = nullptr;
}
};
void insert(Trie* &node, int x, int poz, int ind){
bool aux;
(x & (1 << poz)) ? aux = 1 : aux = 0;
if(node -> children[aux] == nullptr){
node -> children[aux] = new Trie();
}
if(poz == 0){
node -> children[aux] -> ind = ind;
return;
}
insert(node -> children[aux], x, poz - 1, ind);
}
pair<int, int> query(Trie* node, int x, int poz, int mask){
bool aux;
(x & (1 << poz)) ? aux = 1 : aux = 0;
if(poz == -1){
return make_pair(mask, node -> ind);
}
else if(node -> children[!aux] != nullptr){
return query(node -> children[!aux], x, poz - 1, (mask | (1 << poz)));
}
return query(node -> children[aux], x, poz - 1, (mask | (1 << poz)) ^ (1 << poz));
}
int n, best = -1, lft = -1, rgt = -1;
int v[N_MAX], sp[N_MAX];
Trie* root;
void solve(){
cin >> n;
root = new Trie();
insert(root, 0, 20, 0);
for(int i = 1; i <= n; ++i){
cin >> v[i];
sp[i] = sp[i - 1] ^ v[i];
pair<int, int> ans = query(root, sp[i], 20, 0);
if(best < ans.first){
best = ans.first;
lft = ans.second + 1;
rgt = i;
}
insert(root, sp[i], 20, i);
}
cout << best << " " << lft << " " << rgt << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
freopen(INFILE, "r", stdin);
freopen(OUTFILE, "w", stdout);
cin.tie(0), cout.tie(0);
solve();
return 0;
}