Pagini recente » Cod sursa (job #357938) | Cod sursa (job #3348636) | Cod sursa (job #2750754) | Cod sursa (job #1628640) | Cod sursa (job #3349464)
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
const int NMAX=100007,BITS=21;
int n;
int v[NMAX];
int sp[NMAX];
int l,r,maxx;//vrem r min
struct node{
int val;
vector<int> ind;
node *zero,*one;
node(){
val=0;
ind.clear();
zero=nullptr;
one=nullptr;
};
};
node* root=new node();
void add(int x,int idx){
int b=1<<20;
node* nod=root;
while(b>0)
{
int dif=int(int(x)&int(b));
if(dif==0)
{
if(nod->zero==nullptr)
{
nod->zero=new node();
}
nod=nod->zero;
}
else
{
if(nod->one==nullptr)
{
nod->one=new node();
}
nod=nod->one;
}
b=b>>1;
}
nod->val++;
nod->ind.push_back(idx);
}
//gasim cel mai apropiat de x, cu cel mai mare indice mai mic sau egal cu pos
struct per{
int val,ind;
};
per el;
per fin(int x,int pos)
{
int b=1<<20;
node* nod=root;
int valoare=0;
while(b>0)
{
int dif=int(int(x)&int(b));
if(dif==0)
{
if(nod->zero==nullptr)
{
valoare+=b;
nod=nod->one;
}
else
{
nod=nod->zero;
}
}
else
{
if(nod->one==nullptr)
{
nod=nod->zero;
}
else
{
valoare+=b;
nod=nod->one;
}
}
b=b>>1;
}
//avEM VECTORUL nod->id
//Vrem nodul
vector<int>*ad=&(nod->ind);
int st=0,dr=ad->size()-1;
int ras=-1;
//cout<<ad->size()<<" niggers\n";
//cout<<"\n";
while(st<=dr)
{
int mij=(st+dr)/2;
if((*ad)[mij]<=pos)
{
ras=mij;
st=mij+1;
}
else
{
dr=mij-1;
}
}
if(ras!=-1)
{
el.ind=(*ad)[ras];
el.ind=(*ad)[0];
}
else
{
el.ind=-1;
}
el.val=valoare;
return el;
}
int main()
{
in>>n;
add(0,0);
for(int i=1;i<=n;i++)
{
in>>v[i];
sp[i]=sp[i-1]^v[i];
add(sp[i],i);
}
int opos=(1<<21)-1;
for(int i=1;i<=n;i++)
{
per epic=fin(opos-sp[i],i-1);
epic.val=epic.val^sp[i];
if(epic.ind!=-1)
{
if(epic.val>maxx)
{
maxx=epic.val;
l=epic.ind+1;
r=i;
}
}
}
out<<maxx<<" "<<l<<" "<<r;
}