Pagini recente » Cod sursa (job #1414045) | Cod sursa (job #1373247) | Cod sursa (job #2279876) | Cod sursa (job #2018231) | Cod sursa (job #2297679)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, prefix, ans, start, stop;
struct Trie{
int value, poz;
Trie *next[2];
Trie(){
value = poz = 0;
next[0] = next[1] = NULL;
}
};
Trie *T = new Trie;
void Insert(Trie *L, int i)
{
Trie *nod = L;
for(int i = 22; i >= 0; i--)
{
bool val = (prefix&(1<<i));
if(nod->next[val] == NULL)
nod->next[val] = new Trie;
nod = nod->next[val];
}
nod->value = prefix;
nod->poz = i;
}
void Xor(Trie *nod, int st)
{
for(int i = 22; i >= 0; i--)
{
bool val = (prefix&(1<<i));
if(nod->next[1-val])
nod = nod->next[1-val];
else
if(nod->next[val])
nod = nod->next[val];
}
int subarray = ((nod->value)^prefix);
if(subarray >= prefix)
{
if(subarray > ans)
{
ans = subarray;
start = nod->poz+1;
stop = st;
}
}
else
if(prefix > ans)
{
ans = prefix;
start = 1;
stop = st;
}
}
int main()
{
fin >> n;
for(int i = 1; i <= n; i++)
{
int x;
fin >> x;
prefix = prefix^x;
Insert(T, i);
Xor(T, i);
}
fout << ans << " " << start << " " << stop;
return 0;
}