Pagini recente » Cod sursa (job #2386931) | Cod sursa (job #3290333) | Cod sursa (job #1028858) | Cod sursa (job #2610271) | Cod sursa (job #2990794)
#include <iostream>
using namespace std;
const int nmax = 1e5 + 2;
struct node {
node* child[2];
int fin;
};
node* getnode ()
{
node *ret = new node;
ret->child[0] = 0;
ret->child[1] = 0;
ret->fin = 0;
return ret;
}
void addNum (node* root , int x, int b , int index)
{
bool bit = ((x & (1 << b)) > 0) ? 1 : 0;
if (root->child[bit] == 0)
{
root->child[bit] = getnode();
}
if (b == 0) root->child[bit]->fin = index;
else {
addNum(root->child[bit] , x , b-1 , index);
}
}
pair<int , int> query (node* nod , int x , int b , int mask)
{
bool bit = ((x & (1 << b)) > 0) ? 1 : 0;
pair<int , int> rez;
if (b == -1) {
return {mask , nod->fin};
}
else if (nod->child[bit^1] != 0)
{
return query(nod->child[bit^1] , x , b-1 , (mask | (1 << b)));
}
else {
return query(nod->child[bit] , x , b-1 , (mask | (1 << b)) - (1 << b));
}
}
int xp[nmax];
int a[nmax];
int main ()
{
freopen("xormax.in" , "r" , stdin);
freopen("xormax.out" , "w" , stdout);
int n; cin >> n;
node* root = getnode();
addNum(root , xp[0] , 20 , 0);
int maxXor = -1;
int st = -1 , dr = -1;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
xp[i] = (xp[i-1] ^ a[i]);
pair<int , int> crt = query(root , xp[i] , 20 , 0);
if (crt.first > maxXor)
{
st = crt.second;
dr = i;
maxXor = crt.first;
}
addNum(root , xp[i] , 20 , i);
}
cout << maxXor << ' ' << st + 1 << ' ' << dr << '\n';
}