Pagini recente » Cod sursa (job #3253172) | Borderou de evaluare (job #2685718) | Monitorul de evaluare | Cod sursa (job #1851116) | Cod sursa (job #3135108)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
const int dim=1<<17;
char next_ch()
{
static int bp=dim;
static char buff[dim];
if(bp==dim)
{
fread(buff,1,dim,stdin);
bp=0;
}
return buff[bp++];
}
void get(int &a)
{
a=0;
char ch;
do{
ch=next_ch();
}while(ch<'0'||'9'<ch);
do{
a=a*10+ch-'0';
ch=next_ch();
}while('0'<=ch&&ch<='9');
}
int sor[100001];
map <int, int> mp[21];
struct Trie{
int last, nivel;
Trie *zero, *unu;
Trie(int ult){
zero = unu = NULL;
last = ult;
nivel = 21;
}
};
Trie *root = new Trie(-1);
void baga(Trie *nod, int poz)
{
nod->last = poz;
if(nod->nivel == 0)
return;
if((1 << (nod->nivel - 1)) & sor[poz])
{
if(nod->unu == NULL)
{
nod->unu = new Trie(poz);
nod->unu->nivel = nod->nivel - 1;
}
baga(nod->unu, poz);
}
else
{
if(nod->zero == NULL)
{
nod->zero = new Trie(poz);
nod->zero->nivel = nod->nivel - 1;
}
baga(nod->zero, poz);
}
}
int p;
int cauta(Trie *nod, int poz)
{
if(nod->nivel == 0)
{
p = nod->last;
return 0;
}
if((1 << (nod->nivel - 1)) & sor[poz])
{
if(nod->zero != NULL)
return (1 << (nod->nivel - 1)) + cauta(nod->zero, poz);
else
return cauta(nod->unu, poz);
}
else
{
if(nod->unu != NULL)
return (1 << (nod->nivel - 1)) + cauta(nod->unu, poz);
else
return cauta(nod->zero, poz);
}
}
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, x;
get(n);
for(int i = 1; i <= n; i++)
{
get(x);
sor[i] = sor[i - 1] ^ x;
}
root->last = 3;
baga(root, 0);
int max1 = -1, st = -1, dr = -1;
for(int i = 1; i <= n; i++)
{
x = cauta(root, i);
if(x > max1)
{
max1 = x;
st = p + 1;
dr = i;
}
baga(root, i);
}
cout << max1 << " " << st << " " << dr;
return 0;
}