Pagini recente » Cod sursa (job #361919) | Cod sursa (job #1001819) | Cod sursa (job #2069276) | Cod sursa (job #426224) | Cod sursa (job #2298033)
#include<fstream>
#include<string>
#include<set>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n,a[100001],valmax,incmax,sfmax,x;
class Trie
{ public:
Trie *fii[2];
int val;
set<int>elem;
Trie()
{val=0;
for(int i=0;i<=1;i++)
fii[i]=0;
}
int element(int x)
{
set<int>::iterator t;
t=elem.lower_bound(x);
return *t;
}
}*rad=new Trie();
void ad_number(int x,Trie *q,const int n,const int indice)
{
if(x==-1)
{ q->val=n;
(q->elem).insert(indice);
return;
}
if(q->fii[!!(n&(1<<x))]==0) // s ar putea sa apara probleme aici;
q->fii[!!(n&(1<<x))]=new Trie();
ad_number(x-1,q->fii[!!(n&(1<<x))],n,indice);
}
int * find_sol(int n,int el,Trie *q,int x)
{
if(x==-1)
{
static int v[2];
v[0]=(n^(q->val));
v[1]=q->element(el);
return v;
}
if(q->fii[!(n&(1<<x))]!=0)
return find_sol(n,el,q->fii[!(n&(1<<x))],x-1);
return find_sol(n,el,q->fii[!!(n&(1<<x))],x-1);
}
int main()
{
f>>n;
f>>a[1];
valmax=a[1];
incmax=1;
sfmax=1;
for(int i=2;i<=n;i++)
{
f>>x;
a[i]=(x^a[i-1]);
ad_number(21,rad,a[i],i);
}
for(int i=1;i<=n-1;i++)
{
int *v;
v=find_sol(a[i],i,rad,21);
if(v[0]>valmax)
{
incmax=i+1;
sfmax=v[1];
valmax=v[0];
}
else if(v[0]==valmax)
{
if(v[1]>sfmax)
{
sfmax=v[1];
incmax=i+1;
}
else if(v[1]==sfmax)
{
if((v[1]-i+1)<(sfmax-incmax))
{
sfmax=v[1];
incmax=i+1;
}
}
}
}
if(a[n]>valmax)
{sfmax=n;
valmax=a[n];
incmax=1;
}
else if(a[n]==valmax)
{
if(sfmax<n)
{
sfmax=n;
incmax=1;
}
}
g<<valmax<<' '<<incmax<<' '<<sfmax;
return 0;
}