Pagini recente » Cod sursa (job #1821982) | Cod sursa (job #1616808) | Cod sursa (job #2968077)
#include <bits/stdc++.h>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
struct Trie_Nod
{
int nrc;
Trie_Nod* fii[2];
Trie_Nod()
{
nrc = 0;
for (int i = 0; i < 2; i++)
fii[i] = NULL;
}
};
Trie_Nod* root = new Trie_Nod;
int n,sp[100005],a[100005];
int maxim,st,dr;
void update(int x)
{
int bits[25];
for (int i = 20; i >= 0; i--)
{
bits[i] = x % 2;
x /= 2;
}
Trie_Nod* nod = root;
root->nrc++;
for (int i = 0; i <= 20; i++)
{
int p = bits[i];
if (nod->fii[p] == NULL)
nod->fii[p] = new Trie_Nod;
nod = nod->fii[p];
nod->nrc++;
}
}
void query(int x,int poz)
{
int bits[25];
for (int i = 20; i >= 0; i--)
{
bits[i] = x % 2;
x /= 2;
}
Trie_Nod* nod = root;
int ans = 0;
for (int i = 0; i <= 20; i++)
{
ans *= 2;
int p = 1 - bits[i];
if (nod->fii[p] == NULL or nod->fii[p]->nrc == 0)
{
p = 1 - p;
nod = nod->fii[p];
}
else
{
ans++;
nod = nod->fii[p];
}
}
if (ans > maxim)
{
dr = poz;
maxim = ans;
}
}
int main()
{
in >> n;
for (int i = 1; i <= n; i++)
in >> a[i];
for (int i = 1; i <= n; i++)
sp[i] = sp[i - 1] ^ a[i];
update(0);
for (int i = 1; i <= n; i++)
{
update(sp[i]);
query(sp[i],i);
}
out << maxim << ' ';
int xr = 0;
for (int i = dr; i >= 1; i--)
{
xr ^= a[i];
if (xr == maxim)
{
st = i;
break;
}
}
out << st << ' ' << dr;
return 0;
}