Pagini recente » Cod sursa (job #1346644) | Cod sursa (job #1325665) | Cod sursa (job #1763409) | Cod sursa (job #2973569) | Cod sursa (job #2890069)
#include<bits/stdc++.h>
using namespace std;
struct Trie
{
int poz;
Trie *leg[2];
Trie(int p)
{
poz = p;
leg[0] = leg[1] = NULL;
}
};
Trie *rad;
FILE* fin = fopen("xormax.in", "r");
FILE* fout = fopen("xormax.out", "w");
void Adauga(int w, int ind)
{
int i, j;
Trie *q, *p = rad;
for (i = 20; i >= 0; i--)
{
j = (w >> i) & 1;
if (p->leg[j] != NULL) p = p->leg[j];
else
{
q = new Trie(0);
p->leg[j] = q;
p = q;
}
}
if (p->poz == 0) p->poz = ind;
}
void ValMax(int w, int &M, int &P)
{
int i, j;
Trie *p = rad;
M = 0;
for (i = 20; i >= 0; i--)
{
j = (w >> i) & 1;
if (p->leg[1-j] != NULL)
{
M = M | (1 << i);
p = p->leg[1 - j];
}
else if (p->leg[j] != NULL) p = p->leg[j];
else {P = p->poz; return;}
}
P = p->poz;
}
int main()
{
int n, i, w, x, answer = -1, st, dr, v, P;
rad = new Trie(0);
fscanf(fin, "%d", &n);
w = st = dr = 0;
for (i = 1; i <= n; i++)
{
fscanf(fin, "%d", &x);
if (answer < x)
{
answer = x;
st = dr = i;
}
w = w ^ x;
if (i > 1)
{
ValMax(w, v, P);
if (answer < v)
{
answer = v;
st = P + 1; dr = i;
}
}
Adauga(w, i);
}
fprintf(fout, "%d %d %d", answer, st, dr);
return 0 ;
}