Pagini recente » Cod sursa (job #331025) | Cod sursa (job #2072484) | Cod sursa (job #2130006) | Cod sursa (job #1271498) | Cod sursa (job #1593943)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n,k,i,j,a,b,c,bit,y,poz,rasp,st,dr,p,x,r;
int v[100005];
struct Trie
{
Trie* exista[2];
int pozitie;
Trie()
{
memset(exista, 0 , sizeof(exista));
pozitie=0;
}
};
int find(int bit, Trie* t)
{
bool xx;
if(a&bit)
xx = 1;
else
xx = 0;
if(bit == 0)
return t->pozitie;
if(t->exista[!xx] != 0)
{
if(bit > 1)
return find(bit/2, t->exista[!xx]);
else
return find(0, t->exista[!xx]);
}
else
{
if(bit > 1)
return find(bit/2, t->exista[xx]);
else
return find(0, t->exista[xx]);
}
}
void add(int bit, Trie* t)
{
bool xx;
if(a&bit)
xx = 1;
else
xx = 0;
if(bit == 0)
{
t->pozitie = i;
return ;
}
if(t->exista[xx] == 0)
t->exista[xx] = new Trie;
if(bit > 1)
add(bit/2, t->exista[xx]);
else
add(0, t->exista[xx]);
}
int main()
{
fin >> n;
Trie *t = new Trie;
bit = 1 << 20;
add(bit, t);
for(i = 1; i <= n; i++)
{
fin >> v[i];
v[i] ^= v[i - 1];
a = v[i];
poz = find(bit,t);
if((a ^ v[poz]) > rasp)
{
rasp = a ^ v[poz];
st = poz + 1;
dr = i;
}
add(bit, t);
}
fout << rasp << " " << st << " " << dr;
}