Pagini recente » Borderou de evaluare (job #1755158) | Borderou de evaluare (job #388675) | Borderou de evaluare (job #2012559) | Borderou de evaluare (job #944062) | Cod sursa (job #3146922)
#include <bits/stdc++.h>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
int sor[100001];
int st = 0, dr = 1;
struct Trie{
int lastAp;
Trie *fiu[2];
Trie(){
fiu[0] = fiu[1] = NULL;
lastAp = -1;
}
};
Trie *root = new Trie;
void cauta(Trie *nod, int poz, int bit)
{
if(bit == -1)
{
if((sor[poz] ^ sor[nod->lastAp]) > (sor[dr] ^ sor[st]))
{
dr = poz;
st = nod->lastAp;
}
return;
}
int f = 1;
if(sor[poz] & (1 << bit))
f = 0;
if(nod->fiu[f] == NULL)
cauta(nod->fiu[1 ^ f], poz, bit - 1);
else
cauta(nod->fiu[f], poz, bit - 1);
}
void baga(Trie *nod, int poz, int bit)
{
if(bit == -1)
{
nod->lastAp = poz;
return;
}
int f = 0;
if(sor[poz] & (1 << bit))
f = 1;
if(nod->fiu[f] == NULL)
nod->fiu[f] = new Trie;
baga(nod->fiu[f], poz, bit - 1);
}
int main()
{
int n, x;
in >> n;
for(int i = 1; i <= n; i++)
{
in >> x;
sor[i] = sor[i - 1] ^ x;
}
baga(root, 0, 20);
for(int i = 1; i <= n; i++)
{
cauta(root, i, 20);
baga(root, i, 20);
}
out << (sor[dr] ^ sor[st]) << " " << st + 1 << " " << dr;
return 0;
}