Pagini recente » Borderou de evaluare (job #1908115) | Borderou de evaluare (job #1365031) | Borderou de evaluare (job #2363933) | Borderou de evaluare (job #733078) | Cod sursa (job #2662626)
#include <bits/stdc++.h>
#define NMAX 100003
using namespace std;
FILE* fin=fopen("xormax.in","r");
FILE* fout=fopen("xormax.out","w");
struct bitTrie{
struct bt_node{
int val=-1;
bt_node *children[2]={NULL,NULL};
}*root=new bt_node;
void insert(int x, int val){
bt_node* curr=root;
for(int i=20;i>=0;i--){
if(curr->children[x>>i&1]==NULL)
curr->children[x>>i&1]=new bt_node;
curr=curr->children[x>>i&1];
}
curr->val=val;
}
int getMax(int x){
bt_node* curr=root;
for(int i=20;i>=0;i--){
if(curr->children[!(x>>i&1)]!=NULL){
curr=curr->children[!(x>>i&1)];
}
else{
curr=curr->children[x>>i&1];
}
}
return curr->val;
}
}bitwise_trie;
int prefXor[NMAX];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,x,ans=-1,l,r;
fscanf(fin,"%d",&n);
bitwise_trie.insert(0,-1);
for(int i=0;i<n;i++){
fscanf(fin,"%d",&x);
prefXor[i]=(i?prefXor[i-1]:0)^x;
int p=bitwise_trie.getMax(prefXor[i]);
int Xor=prefXor[i]^(p>=0?prefXor[p]:0);
if(Xor>ans){
l=p+2;
r=i+1;
ans=Xor;
}
bitwise_trie.insert(prefXor[i],i);
}
fprintf(fout,"%d %d %d",ans,l,r);
return 0;
}