Pagini recente » Cod sursa (job #3347427) | Cod sursa (job #119708) | Cod sursa (job #1065608) | Cod sursa (job #26857) | Cod sursa (job #3351749)
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3","unroll-loops")
const int maxn=1e5+5;
int prefxor[maxn];
struct Node{
int endd;
vector<int> next;
Node(){
endd=0;
next.assign(2,-1);
}
};
struct Trie{
vector<Node> t;
Trie(){
t.push_back(Node());
}
void insertt(int nr,int idd){
int u=0;
t[u].act+=1;
for(int i=20;i>=0;i--){
bool val=(((1<<i)&nr))>>i;
if(t[u].next[val]==-1){
t[u].next[val]=t.size();
t.push_back(Node());
}
u=t[u].next[val];
t[u].act+=1;
}
t[u].endd=idd;
}
pair<int,int> calc(int nr){
int u=0;
int x=0;
for(int i=20;i>=0;i--){
bool val=1-(((1<<i)&nr)>>i);
//cout<<i<<" "<<nr<<" "<<val<<endl;
if(t[u].next[val]!=-1){
x+=val*(1<<i);
u=t[u].next[val];
}else{
val=1-val;
//if(t[u].endd)return x;
x+=val*(1<<i);
u=t[u].next[val];
}
}
return {x,t[u].endd};
}
};
signed main()
{
ifstream cin("xormax.in");
ofstream cout("xormax.out");
Trie trie;
int n;
cin>>n;
int maxi=-1;
int l,r;
for(int i=1;i<=n;i++){
int x;
cin>>x;
prefxor[i]=prefxor[i-1]^x;
if(prefxor[i]>maxi){
maxi=prefxor[i];
l=1;
r=i;
}
}
for(int i=n;i>=1;i--){
trie.insertt(prefxor[i],i);
int best,idd;
tie(best,idd)=trie.calc(prefxor[i]);
if((best^prefxor[i])>maxi || (maxi==(best^prefxor[i]) && idd<r) || (maxi==(best^prefxor[i]) && idd==r && (r-l+1)>idd-i)){
l=i+1;
r=idd;
maxi=best^prefxor[i];
}
}
cout<<maxi<<" "<<l<<" "<<r;
return 0;
}