Pagini recente » Cod sursa (job #1459043) | Cod sursa (job #253442) | Cod sursa (job #2017903) | Cod sursa (job #1624697) | Cod sursa (job #2907233)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n;
int v[100009];
class trie
{
public:
trie *fiu[2];
int nr=0;
trie()
{
fiu[0]=nullptr;
fiu[1]=nullptr;
}
void insereaza(int x, int poz_bit, int ind)
{
if(poz_bit>=0)
{
int val=(x&(1<<poz_bit));
bool bit=0;
if(val>0)
{
bit=1;
}
if(fiu[bit]==nullptr)
{
fiu[bit]=new trie();
}
fiu[bit]->insereaza(x,poz_bit-1,ind);
}
else
{
nr=ind;
return;
}
}
int cautare(int x, int poz_bit)
{
if(poz_bit>=0)
{
int val=(x&(1<<poz_bit));
bool bit;
if(val==0)
{
bit=1;
}
else
{
bit=0;
}
if(fiu[bit]!=nullptr)
{
return fiu[bit]->cautare(x,poz_bit-1);
}
else
{
return fiu[1-bit]->cautare(x,poz_bit-1);
}
}
else
{
return nr;
}
}
};
int main()
{
fin>>n;
trie *radacina=new trie();
int maxim=-1, poz_f, poz_i, poz_ini;
radacina->insereaza(0,20,0);
for(int i=1;i<=n;i++)
{
fin>>v[i];
v[i]=(v[i-1]^v[i]);
int complementar=radacina->cautare(v[i],20);
int rez=(v[i]^v[complementar]);
if(rez>maxim)
{
maxim=rez;
poz_ini=complementar;
poz_f=i;
}
radacina->insereaza(v[i],20,i);
}
fout<<maxim<<' '<<poz_ini+1<<' '<<poz_f;
return 0;
}