Pagini recente » Clasament 49maimare48 | Cod sursa (job #387210) | Cod sursa (job #2118783) | Cod sursa (job #869016) | Cod sursa (job #3135100)
#include <bits/stdc++.h>
using namespace std;
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;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> x;
sor[i] = sor[i - 1] ^ x;
}
root->last = 3;
baga(root, 0);
int max1 = 0, st, dr;
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;
}