Pagini recente » Cod sursa (job #425827) | Cod sursa (job #2546568) | Cod sursa (job #1141637) | Cod sursa (job #720292) | Cod sursa (job #2570908)
#include <fstream>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
//----------------------------------------
///Globale
int n,st,dr,rasp,d[1000001];
struct trie
{
trie *z,*u;
int who;
trie()
{
z = NULL;
u = NULL;
}
}*r;
//----------------------------------------
///Functii
void citire();
void rezolvare();
void afisare();
//----------------------------------------
int main()
{
citire();
rezolvare();
afisare();
}
//----------------------------------------
void afisare()
{
g << rasp << " " << st << " " << dr;
}
//----------------------------------------
int cauta(int val,int bit,trie *nod)
{
if(bit == -1)
return nod -> who;
int x = val & (1 << bit);
if(x == 0)
{
if(nod -> u != NULL)
return cauta(val,bit - 1,nod -> u);
else
return cauta(val,bit - 1,nod -> z);
}
else
{
if (nod -> z != NULL)
return cauta(val,bit - 1,nod -> z);
else
return cauta (val,bit - 1,nod -> u);
}
}
//----------------------------------------
trie* adauga(int i,int bit,trie*nod)
{
if(nod == NULL)
nod = new trie;
if(bit == -1)
{
nod -> who = i;
return nod;
}
int x = d[i] & (1 << bit);
if(x == 0)
nod -> z = adauga(i,bit - 1,nod -> z);
else
nod -> u = adauga(i,bit - 1,nod -> u);
return nod;
}
//----------------------------------------
void rezolvare()
{
rasp = -1;
r = adauga(0,21,r);
for(int i = 1; i <= n; ++i)
{
int gasit = cauta(d[i],21,r);
if((d[gasit] ^ d[i]) > rasp)
{
rasp = d[gasit] ^ d[i];
dr = i;
st = gasit + 1;
}
r = adauga(i,21,r);
}
}
void citire()
{
f >> n;
for(int i = 1; i <= n; ++i)
{
int x;
f >> x;
d[i] = d[i - 1] ^ x;
}
}