Cod sursa(job #581305)

Utilizator drywaterLazar Vlad drywater Data 13 aprilie 2011 23:31:52
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
/*#include <stdio.h>
int n,a,b,i,x[100101],q,max=-1;
struct Trie
{
    int poz;
    Trie *fiu[2];
    Trie()
    {
        poz=0;
        fiu[0]=fiu[1]=0;
    }
};
Trie *t=new Trie;
int caut(int val,int bit)
{
    Trie *R=t;
    while (bit!=-1)
    {
        int x=((val&(1<<bit))>>bit);
        if (R->fiu[x^1]) R=R->fiu[x^1];
        else R=R->fiu[x];
        bit--;
    }
    if (max<val^x[R->poz])
    {
        max=val^x[R->poz];
        a=(R->poz)+1;
        b=i;
    }
    return 0;

}
int ins(Trie *nod,int val,int bit)
{
    if (bit==-1)
    {
        nod->poz=i;
        return 0;
    }
    int x=(((1<<bit)&val)>>bit);
    if (nod->fiu[x]==0) nod->fiu[x]=new Trie;
    bit--;
    ins(nod->fiu[x],val,bit);
}
int main(void)
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    ins(t,0,24);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&q);
        x[i]=x[i-1]^q;
        caut(x[i],24);
        ins(t,x[i],24);

    }
    printf("%d %d %d\n",max,a,b);
    return 0;
}*/
#include <cstdio>
#include <string>
#include <cstring>

#define MAXN 100010
using namespace std;


struct Trie {
	Trie *fiu[2];
	int end;
	Trie () {
		fiu[0] = fiu[1] = 0;
		end = 0;
	}
};

Trie *T = new Trie;
int N, i, X[MAXN], Sol = -1, SolX, SolY;
void Insert (Trie *R, int Val, int Bit)
{
	if (Bit == -1) {

		R -> end = i;
		return ;
	}

	int x = (((1 << Bit) & Val) >> Bit);

	if (R -> fiu[x] == 0)
		R -> fiu[x] = new Trie;

	Bit -= 1;

	Insert (R -> fiu[x], Val, Bit);
}
void Query (int Val, int Bit)
{
	Trie *R = T;

	while (Bit != -1) {
		int x = ((Val & (1 << Bit)) >> Bit);
		if (R -> fiu[x ^ 1])
			R = R -> fiu[x ^ 1];
		else R = R -> fiu[x];

		Bit -= 1;
	}

	if (Sol < (Val ^ X[R -> end])) {

		Sol = Val ^ X[R -> end];
		SolX = R -> end + 1;
		SolY = i;
	}


}
int main ()
{

	freopen ("xormax.in", "r", stdin);
	freopen ("xormax.out", "w", stdout);

	scanf ("%d\n", &N);
	int A;

	Insert (T, 0, 24);

	for (i = 1; i <= N; i++) {

		scanf ("%d", &A);
		X[i] = X[i - 1] ^ A;

		Query (X[i], 24);
		Insert (T, X[i], 24);
	}

	printf ("%d %d %d\n", Sol, SolX, SolY);

	return 0;
}