Pagini recente » Cod sursa (job #2366338) | Cod sursa (job #673283) | Cod sursa (job #1414411) | Cod sursa (job #1956998) | Cod sursa (job #2533135)
#include <cstdio>
using namespace std;
FILE *fin = fopen("xormax.in", "r");
FILE *fout = fopen("xormax.out", "w");
int n,i,x,nrbit,s[100005];
struct trie{
int poz;
trie *f[3];
trie()
{
poz = 0;
f[0] = f[1] = 0;
}
};
trie *root = new trie;
void adauga(trie *r, int val, int bit, int pozitie)
{
if (bit < 0)
r->poz = pozitie;
else
{
int fiu = ((val>>bit)&1);
if (r->f[fiu] == NULL)
r->f[fiu] = new trie();
adauga(r->f[fiu], val, bit-1, pozitie);
}
}
int query(trie *r, int val, int bit)
{
if (bit < 0)
return r->poz;
else
{
int fiu = ((val>>bit)&1);
if (r->f[1-fiu] == NULL)
query(r->f[fiu], val, bit-1);
else
query(r->f[1-fiu], val, bit-1);
}
}
int main()
{
fscanf(fin, "%d", &n); int maxim = 0;
for (i=1; i<=n; i++)
{
fscanf(fin, "%d", &x);
s[i] = (s[i-1]^x);
if (s[i] > maxim)
maxim = s[i];
}
while (maxim > 0)
{
nrbit++;
maxim /= 2;
}
adauga(root, 0, nrbit, 0); maxim = -1; int st = 0; int dr = 0;
for (i=1; i<=n; i++)
{
int bestpoz = query(root, s[i], nrbit);
if ((s[bestpoz]^s[i]) > maxim)
{
maxim = (s[bestpoz]^s[i]);
st = bestpoz+1; dr = i;
}
adauga(root, s[i], nrbit, i);
}
fprintf(fout, "%d %d %d", maxim, st, dr);
return 0;
}