Pagini recente » Cod sursa (job #831960) | Cod sursa (job #2795126) | Cod sursa (job #710000) | Cod sursa (job #809703) | Cod sursa (job #3295711)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, a[100005], k, b[25], prefix, sol, start, finish;
struct Trie{
int poz;
Trie *fiu[22];
Trie()
{
poz = -1;
memset(fiu, 0, sizeof(fiu));
}
};
Trie *T = new Trie;
void Insert(Trie *nod, int ind, int pas)
{
if(ind == k + 1)
{
nod->poz = pas;
return ;
}
if(nod->fiu[b[ind]] == 0)
{
Trie *nod2 = new Trie;
nod->fiu[b[ind]] = nod2;
}
Insert(nod->fiu[b[ind]], ind + 1, pas);
}
pair<int, int> Find(Trie *nod, int bit, int nr, int scad)
{
int i, bit_1, bit_2;
bit_1 = bit_2 = -1;
for(i = bit;i >= 0 && bit_1 == -1;i--)
if(nod->fiu[i] && !((1 << i) & prefix)) bit_1 = i;
else if(nod->fiu[i]) bit_2 = i;
if(bit_1 > bit_2)
return Find(nod->fiu[bit_1], bit_1 - 1, nr + (1 << bit_1), scad);
if(bit_2 > -1 && bit_1 == -1)
{
if(nod->poz > -1)
return {nr + prefix - scad, nod->poz};
return Find(nod->fiu[bit_2], bit_2 - 1, nr, scad + (1 << bit_2));
}
if(bit_1 != bit_2)
return Find(nod->fiu[bit_1], bit_1 - 1, nr + (1 << bit_1), scad);
return {nr + prefix - scad, nod->poz};
}
int main()
{
int i, j, pozitie;
pair<int, int> maxi;
fin >> n;
for(i = 1;i <= n;i++)
fin >> a[i];
sol = -1;
for(i = 1;i <= n;i++)
{
prefix ^= a[i];
k = 0;
for(j = 20;j >= 0;j--)
if(prefix & (1 << j))
b[++k] = j;
maxi = Find(T, 20, 0, 0);
if(maxi.first > sol)
{
sol = maxi.first;
finish = i;
start = maxi.second + 1;
}
else if(maxi.first == sol && finish - start + 1 > i - maxi.second)
{
start = maxi.second + 1;
finish = i;
}
if(prefix > sol)
{
sol = prefix;
finish = i;
start = 1;
}
Insert(T, 1, i);
}
fout << sol << " " << start << " " << finish << "\n";
fout.close();
return 0;
}