Cod sursa(job #238301)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 1 ianuarie 2009 19:56:36
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <bitset>
#include <utility>
#include <algorithm>
#include <functional>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(x,y) memcpy((x),(y),sizeof((y)))
#define FORit(it,v) for(it = (v).begin();it != (v).end();++it)
#define mp make_pair

#define IN  "xormax.in"
#define OUT "xormax.out"
#define N_MAX 1<<18
#define B_MAX 19
#define bit(x) (1<<(B_MAX+1))-1

typedef pair<int,int> pi;
typedef vector< vector<pi> > VM;

int poz,next,N;
int X[N_MAX],V[N_MAX],P[N_MAX];
char L[N_MAX];
string word;
VM A(1<<18);

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d",&N);
	
	FOR(i,1,N)
		scanf("%d",&V[i]);
}		

II void convert(int x)
{
	int size = B_MAX+1;
	FOR(i,0,B_MAX) word[i] = 0;
	for(;x;word[--size] = x&1,x >>= 1);
}

II void add(int nod,int x)
{
	if(x==B_MAX+1)
	{
		P[nod] = poz;
		return;
	}	
	FOR(i,0,L[nod]-1)
		if(A[nod][i].s == word[x])
		{
			add(A[nod][i].f,x+1);
			return;
		}	
	A[nod].pb( mp(++next,word[x]) );
	add(next,x+1);
	++L[nod];
}

II int querry(int nod,int x)
{
	if(x==B_MAX+1)
		return nod;
	if(L[nod]-1 && A[nod][1].s == word[x])
		return querry(A[nod][1].f,x+1);
	return querry(A[nod][0].f,x+1);	
}

II void solve()
{
	word.resize(B_MAX+1);
	FOR(i,1,N)
		X[i] = X[i-1] ^ V[i];
	
	pair<int, pi> rez;
	rez.f = -1;	
	
	for(int i=N-1;i>=1;--i)
	{
		convert(X[i+1]);
		poz = i+1;
		add(0,0);
		
		convert(X[i] ^ bit(X[i]));
		int nod = querry(0,0);
		if( (X[ P[nod] ] ^ X[i]) > rez.f)
		{
			rez.f = X[ P[nod] ] ^ X[i];
			rez.s.f = i+1;
			rez.s.s = P[nod];
		}	
	}	
	printf("%d %d %d\n",rez.f,rez.s.f,rez.s.s);
}

int main()
{
	scan();
	solve();
	return 0;
}