Pagini recente » Cod sursa (job #1373107) | Cod sursa (job #501070) | Cod sursa (job #634744) | Cod sursa (job #131777) | Cod sursa (job #2394064)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n,i,x,v[100010],x2,y2,ma,ma2,poz,poz2,poz3,poz4,r;
long long put;
struct Trie
{
Trie *fii[2];
};
Trie *t=new Trie();
void adauga(Trie *p,int x,int put)
{
if(put==0)
{
return;
}
if(i==1)
{
//g<<x<<" "<<put<<" "<<x/put%2<<'\n';
}
if(p->fii[(x/put)%2]==NULL)
{
p->fii[(x/put)%2]=new Trie();
}
adauga(p->fii[(x/put)%2],x%put,put/2);
}
int cauta(Trie *p,int put,int x)
{
//g<<put<<'\n';
if(put==0)
{
return 0;
}
if(p->fii[(x/put)^1]!=NULL)
{
return put+cauta(p->fii[(x/put)^1],put/2,x%put);
}
else
{
return cauta(p->fii[(x/put)],put/2,x%put);
}
}
int main()
{
f>>n;
for(i=1; i<=n; i++)
{
f>>x;
v[i]=v[i-1]^x;
if(v[i]>ma)
{
ma=v[i];
poz=i;
poz=i;
poz2=i;
}
}
put=1;
for(i=1; i<=22; i++)
{
put*=2;
}
adauga(t,0,put);
for(i=1; i<=n; i++)
{
ma2=cauta(t,put,v[i]);
if(ma<ma2)
{
r=1;
ma=ma2;
poz=v[i];
poz2=v[i]^ma2;
poz4=i;
}
adauga(t,v[i],put);
}
if(r==0)
{
//g<<ma<<" "<<poz<<" "<<poz2;
return 0;
}
//g<<poz<<" "<<poz2<<'\n';
f.close();
f.open("xormax.in");
f>>n;
for(i=0; i<=n; i++)
{
if(i>=1)
{
f>>x;
v[i]=v[i-1]^x;
}
if(v[i]==poz2 && i<poz4)
{
poz3=i;
}
}
if(poz3>poz4)
{
swap(poz3,poz4);
}
g<<ma<<" "<<poz3+1<<" "<<poz4;
return 0;
}