Pagini recente » Cod sursa (job #1324998) | Cod sursa (job #2465596) | Cod sursa (job #82682) | Cod sursa (job #2352126) | Cod sursa (job #3143171)
#include<bits/stdc++.h>
using namespace std;
struct Trie{
int leftPos;
Trie* children[2];
Trie(){
leftPos = 0;
memset(children, 0, sizeof(children));
}
};
Trie* root = new Trie;
int main(){
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n;
cin >> n;
vector<int> v(1 + n);
for(int i = 1; i <= n; i++){
cin >> v[i];
}
vector<int> prefXor(1 + n, 0);
for(int i = 1; i <= n; i++){
prefXor[i] = prefXor[i - 1] ^ v[i];
}
Trie* cur = root;
for(int j = 20; j >= 0; j--){
if(cur->children[0] == NULL){
cur->children[0] = new Trie;
}
cur = cur->children[0];
cur->leftPos = 0;
}
int leftAns = 0;
int rightAns = 0;
int ans = 0;
for(int i = 1; i <= n; i++){
Trie* cur2 = root;
int val = prefXor[i];
int valCur = 0;
for(int j = 20; j >= 0; j--){
int current;
if(val & (1 << j)){
current = 0;
}
else{
current = 1;
}
valCur ^= (1 << j);
if(cur2 -> children[current] == NULL){
current ^= 1;
valCur ^= (1 << j);
}
cur2 = cur2->children[current];
}
if(valCur > ans){
ans = valCur;
leftAns = cur2->leftPos + 1;
rightAns = i;
}
Trie* cur3 = root;
for(int j = 20; j >= 0; j--){
int current;
if(prefXor[i] & (1 << j)){
current = 1;
}
else{
current = 0;
}
if(cur3->children[current] == NULL){
cur3->children[current] = new Trie;
}
cur3 = cur3->children[current];
cur3->leftPos = i;
}
}
cout << ans << " " << leftAns << " " << rightAns << "\n";
}