Pagini recente » Cod sursa (job #157772) | Cod sursa (job #671691) | Cod sursa (job #233364) | Cod sursa (job #207418) | Cod sursa (job #1481453)
#include<iostream>
#include<fstream>
#include<string.h>
#include<stdlib.h>
using namespace std;
#define NMAX 100001
#define LMAX 21
struct trie {
trie *st,*dr;
trie () {
st=NULL;
dr=NULL;
}
};
char sir[LMAX+1];
int v[NMAX],x[NMAX];
inline int BIT(int x, int nr)
{
return (x & (1<<nr)) != 0;
}
trie* aloca()
{
trie *p;
p=(trie*)malloc(sizeof(trie));
p->st=NULL;
p->dr=NULL;
return p;
}
void adauga(trie *p, char *s)
{
if(*s=='\0') {
return ;
}
if(*s=='0') {
if(p->st==NULL)
p->st=aloca();
adauga(p->st,s+1);
}
else if(*s=='1') {
if(p->dr==NULL)
p->dr=aloca();
adauga(p->dr,s+1);
}
}
int maxim(trie *p, char *s, int bit)
{
if(*s=='\0')
return 0;
if(*s=='0') {
if(p->dr!=NULL)
return (1<<bit)+maxim(p->dr,s+1,bit-1);
return maxim(p->st,s+1,bit-1);
}
else {
if(p->st!=NULL)
return (1<<bit)+maxim(p->st,s+1,bit-1);
return maxim(p->dr,s+1,bit-1);
}
}
int main ()
{
int n,i,sol,j,val,stop;
trie *p;
ifstream f("xormax.in");
ofstream g("xormax.out");
f>>n;
for(i=1;i<=n;i++)
f>>v[i];
f.close();
for(i=1;i<=n;i++)
x[i]=x[i-1]^v[i];
sol=-(1<<30);
memset(sir,0,sizeof(sir));
p=aloca();
for(i=0;i<=LMAX-1;i++)
sir[i]='0';
adauga(p,sir);
for(i=1;i<=n;i++) {
memset(sir,0,sizeof(sir));
for(j=0;j<=LMAX-1;j++)
if(BIT(x[i],j))
sir[LMAX-1-j]='1';
else sir[LMAX-1-j]='0';
val=maxim(p,sir,LMAX-1);
if(val>sol) {
sol=val;
stop=i;
}
adauga(p,sir);
}
for(i=stop;i>=1;i--)
if((x[i]^x[stop])==sol)
break;
g<<sol<<" "<<i+1<<" "<<stop;
g.close();
return 0;
}