Pagini recente » Cod sursa (job #1920278) | Cod sursa (job #1872448) | Cod sursa (job #2472123) | Cod sursa (job #1911612) | Cod sursa (job #2907736)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n;
int v[100009];
string s;
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 get_next_nr(int & poz)
{
int numar = 0;
while(poz<s.size() && s[poz]!=' ')
{
int cif = s[poz] - '0';
numar = numar*10 + cif;
poz++;
}
poz++;
return numar;
}
int main()
{
ios_base::sync_with_stdio(false);
fin>>n;
trie *radacina=new trie();
int maxim=-1, poz_f, poz_i, poz_ini;
radacina->insereaza(0,20,0);
getline(fin,s);
getline(fin,s);
int poz=0;
for(int i=1;i<=n;i++)
{
v[i] = get_next_nr(poz);
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;
}