Pagini recente » Cod sursa (job #982588) | Cod sursa (job #536507) | Cod sursa (job #325381) | Cod sursa (job #2851323) | Cod sursa (job #923354)
Cod sursa(job #923354)
#include <fstream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int BMAX = 23;
const int NMAX = int(1e5)+ 2;
int N;
int stopPos;
struct trie {
trie *son[2];
int pos;
trie() {
pos = 0;
memset(son,0,sizeof(son));
}
};
trie *T;
void insert(trie *t,int val,int k,const int &pos) {
if(k == -1) {
t->pos = max(t->pos,pos);
return;
}
int currentBit = (val>>k) & 1;
if(t->son[currentBit] == NULL) {
t->son[currentBit] = new trie;
}
t = t->son[currentBit];
insert(t,val,k - 1,pos);
}
int getVal(trie *t,int val,int k) {
if(k == -1) {
stopPos = t->pos;
return 0;
}
int currentBit = (val>>k) & 1;
if(t->son[currentBit ^ 1] != NULL) {
t = t->son[currentBit ^ 1];
return (1<<k) + getVal(t,val,k - 1);
}
t = t->son[currentBit];
return getVal(t,val,k - 1);
}
int main()
{
cin>>N;
T = new trie;
int ans = 0;
int leftS, rightS;
leftS = 0, rightS = 0;
insert(T,0,BMAX,0);
int currValue, X = 0;
for(int i = 1;i <= N;i++) {
cin>>currValue;
X ^= currValue;
insert(T,X,BMAX,i + 1);
int bstVal = getVal(T,X,BMAX);
if(bstVal > ans) {
ans = bstVal;
leftS = stopPos;
rightS = i;
}
}
cout<<ans<<" "<<leftS<<" "<<rightS<<"\n";
return 0;
}