Pagini recente » Cod sursa (job #2290487) | Cod sursa (job #2685726) | Cod sursa (job #1777214) | Cod sursa (job #1103798) | Cod sursa (job #2910047)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, x[100005];
int vMax = -1, pLeft, pRight;
struct Trie
{
Trie *leg[2];
int poz;
Trie()
{
poz = 0;
leg[0] = leg[1] = 0;
}
};
Trie *rad = new Trie;
void Add(Trie *nod, int a, int poz, int cnt)
{
bool b;
if(cnt < 0)
{
nod -> poz = poz;
return;
}
b = (a & (1 << cnt));
if(nod -> leg[b] == 0)
nod -> leg[b] = new Trie;
Add(nod -> leg[b], a, poz, cnt - 1);
}
int Find(Trie *nod, int a, int cnt)
{
if(cnt < 0)
return nod -> poz;
bool b = (a & (1 << cnt));
if(nod -> leg[1 - b] != 0)
return Find(nod -> leg[1-b], a, cnt - 1);
return Find(nod -> leg[b], a, cnt - 1);
}
void Rezolvare()
{
Add(rad, 0, 0, 22);
for(int i = 1; i <= n; i++)
{
int j = Find(rad, x[i], 22);
if((x[i] ^ x[j]) > vMax)
{
pLeft = j + 1;
pRight = i;
vMax = (x[i] ^ x[j]);
}
Add(rad, x[i], i, 22);
}
fout << vMax << " " << pLeft << " " << pRight << "\n";
}
int main()
{
int val;
fin >> n ;
for(int i = 1; i <= n; i++)
{
fin >> val;
x[i] = x[i - 1] ^ val;
}
Rezolvare();
return 0;
}