Pagini recente » Cod sursa (job #770928) | Cod sursa (job #2288732) | Cod sursa (job #1574959) | Cod sursa (job #197825) | Cod sursa (job #2058282)
#include<fstream>
#include<string.h>
using namespace std;
ifstream fi("xormax.in");
ofstream fo("xormax.out");
typedef struct trie {bool terminal;struct trie * fiu[2];} NOD, *TRIE;
void adauga(TRIE &T, char *p)
/// se adauga X in T
{
if (T==NULL)
{
T=new NOD;
T->terminal=false;
for (int i=0;i<=1;i++)
T->fiu[i]=NULL;
adauga(T,p);
}
if ((*p)=='\0')
T->terminal=true;
else
adauga(T->fiu[(*p)-'0'],p+1);
}
void cauta(TRIE T, char *p, int &rez)
/// p este sirul fata de care ma opun
{
if (T->terminal==true)
return;
if (*p=='0')
if (T->fiu[1]!=NULL)
{
rez=rez*2+1;
cauta(T->fiu[1],p+1,rez);
}
else
{
rez=rez*2;
cauta(T->fiu[0],p+1,rez);
}
else
if (T->fiu[0]!=NULL)
{
rez=2*rez;
cauta(T->fiu[0],p+1,rez);
}
else
{
rez=2*rez+1;
cauta(T->fiu[1],p+1,rez);
}
}
TRIE T;
int N;
int A[100001];
int X[100001];
char B[23];
int k,v,dr,rez,val,ind,ind2;
int main()
{
fi>>N;
for (int i=1;i<=N;i++)
{
fi>>A[i];
X[i]=X[i-1]^A[i];
}
for (int i=1;i<=N;i++)
{
/// se introduce numarul corespunzator lui X[i] in trie-ul T
/// se obtin siruri de cate 21 de biti
memset(B,'0',sizeof(B));
if(X[i]==0)
B[21]='\0';
else
{
B[21]='\0';
dr=20;
val=X[i];
while(val)
{
B[dr]=(char)(val%2+'0');
dr--;
val/=2;
}
}
adauga(T,B);
val=0;
cauta(T,B,val);
val^=X[i];
if(val>rez)
{
rez=val;
ind=i;
}
}
fo<<rez<<" ";
for(int i=1; i<=ind; i++)
{
if((X[i]^X[ind])==rez)
{
ind2=i+1;
}
}
fo<<ind2<<" "<<ind<<"\n";
fi.close();
fo.close();
return 0;
}