Pagini recente » Cod sursa (job #2405370) | Cod sursa (job #228004) | Cod sursa (job #2925616) | Cod sursa (job #1310836) | Cod sursa (job #936352)
Cod sursa(job #936352)
#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;
int N;
int stopPos;
struct trie {
trie *son[2];
int pos;
trie() {
pos = 0;
memset(son,0,sizeof(son));
}
};
trie *T;
inline void insert(trie *t,const int &val,const int &p) {
for(int k = BMAX - 1;k >= 0;k--) {
int currentBit = (val>>k) & 1;
if(t->son[currentBit] == NULL) {
t->son[currentBit] = new trie;
}
t = t->son[currentBit];
}
t->pos = max(t->pos,p);
}
inline int getVal(trie *t,const int &val,const int &k) {
int ret = 0;
for(int k = BMAX - 1;k >= 0;k--) {
int currentBit = (val>>k) & 1;
if(t->son[currentBit ^ 1] != NULL) {
t = t->son[currentBit ^ 1];
ret += (1<<k);
} else {
t = t->son[currentBit];
}
}
stopPos = t->pos;
return ret;
}
int main()
{
cin>>N;
T = new trie;
int ans;
int leftS, rightS;
ans = 0;
leftS = rightS = 1;
insert(T,0,0);
int currValue, X = 0;
for(int i = 1;i <= N;i++) {
cin>>currValue;
X ^= currValue;
insert(T,X,i + 1);
int bstVal = getVal(T,X,BMAX);
if(bstVal > ans) {
ans = bstVal;
leftS = stopPos;
rightS = i;
}
}
cout<<ans<<" "<<leftS<<" "<<rightS<<"\n";
return 0;
}