Pagini recente » Cod sursa (job #1003752) | Cod sursa (job #1183253) | Cod sursa (job #2903559) | Cod sursa (job #1119704) | Cod sursa (job #1672486)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
# define NR 100005
using namespace std;
struct trie
{
int last;
trie *fiu[3];
trie()
{
last=0;
memset (fiu, 0, sizeof(fiu));
}
};
trie *T=new trie;
int n;
int XOR;
int CI,CS,sol;
int maxx, maxim, I;
int a[NR], var[25];
void readData();
void solve();
void writeData();
void cauta(trie *nod, int *var, int niv);
void update(trie *nod, int *var, int niv, int poz);
int main()
{
readData();
solve();
writeData();
return 0;
}
void update(trie *nod, int *var, int niv, int poz)
{ // pune xoruri in trie
if(niv == maxx)
nod->last=poz;
int CH = *var;
if(niv < maxx)
{
if(nod->fiu[CH] == 0)
nod->fiu[CH] = new trie;
update(nod->fiu[CH], var-1, niv+1, poz);
}
}
void cauta(trie *nod, int *var, int niv)
{
if(niv == maxx)
I = nod->last;
int CH = *var;
int D = 1 - CH;
if(niv < maxx)
{
if (nod->fiu[D] != 0) // cel care trebuie
{
maxim = maxim*2 + 1;
cauta(nod->fiu[D], var-1, niv+1);
}
else
{
maxim = maxim*2;
cauta(nod->fiu[CH], var-1, niv+1);
}
}
}
void readData()
{
ifstream fin("xormax.in");
fin >> n;
for(int i=1; i<=n; ++i)
{
fin >> a[i];
XOR = XOR ^ a[i];
for(int j=21; j>=maxx; --j)
if((1<<j) & XOR)
{
maxx = max(maxx, j);
break;
}
}
fin.close();
}
void solve()
{
XOR = 0;
sol = -1;
update (T, var+maxx, -1, 0);
for(int i=1; i<=n; ++i)
{
XOR = XOR ^ a[i];
for(int j=maxx; j>=0; --j)
if((1<<j) & XOR)
var[j]=1;
else
var[j]=0;
maxim=0;
I=0;
cauta (T, var+maxx, -1);
if(maxim > sol)
{
sol=maxim;
CI=I;
CS=i;
}
update (T, var+maxx, -1, i);
}
}
void writeData()
{
ofstream fout("xormax.out");
fout << sol << " " << CI+1 << " " << CS << endl;
fout.close();
}