Pagini recente » Cod sursa (job #1835817) | Cod sursa (job #258333) | Cod sursa (job #875900) | Cod sursa (job #418586) | Cod sursa (job #2533307)
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n,i,x,maxx,nr,maxim,st,dr,solpoz,s[DIM];
struct trie{
int poz;
trie *f[2];
trie() {
f[0]=f[1]=0;
poz=0;
}
};
trie *r;
void insertTrie(trie *r, int bit,int val,int poz) {
if (bit==-1) {
r->poz=poz;
return;
}
if (((val>>bit)&1)==0) {
if (r->f[0]==nullptr)
r->f[0]=new trie();
insertTrie(r->f[0],bit-1,val,poz);
}
else {
if (r->f[1]==nullptr)
r->f[1]=new trie();
insertTrie(r->f[1],bit-1,val,poz);
}
}
void searchTrie(trie *r,int bit,int val) {
if (bit==-1) {
solpoz=r->poz;
return;
}
int bitval=((val>>bit)&1);
if (r->f[1-bitval]!=0)
searchTrie(r->f[1-bitval],bit-1,val);
else
searchTrie(r->f[bitval],bit-1,val);
}
int main() {
fin>>n>>s[1];
maxim=-1;
for (i=2;i<=n;i++) {
fin>>x;
if (x>maxx)
maxx=x;
s[i]=(x^s[i-1]);
}
while (maxx)
nr++, maxx/=2;
r=new trie();
insertTrie(r,nr,0,0);
for (i=1;i<=n;i++) {
searchTrie(r,nr,s[i]);
if ((s[i]^s[solpoz])>maxim) {
maxim=(s[i]^s[solpoz]);
st=solpoz+1;
dr=i;
}
insertTrie(r,nr,s[i],i);
}
fout<<maxim<<" "<<st<<" "<<dr;
return 0;
}