Cod sursa(job #945436)

Utilizator Marius96Marius Gavrilescu Marius96 Data 1 mai 2013 21:55:16
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<cstdio>

#include<algorithm>

#define idx(x) sv[x].second

using std::pair;
using std::make_pair;

int v[100005];
pair<int, int> sv[100005];

int start, stop, ret=-1;

bool isbetter(int nstart, int nstop, int xr)
{
	if(nstop==0)
		return 0;

	if(nstop<=nstart)
		std::swap(nstop, nstart);
	if(stop<=start)
		std::swap(stop, start);

	if(xr > ret)
		return 1;
	if(xr < ret)
		return 0;

	if(nstop<stop)
		return 1;
	if(nstop>stop)
		return 0;

	return nstart > start;
}

void tryupdate(int nstart, int nstop)
{
	if(isbetter(idx(nstart), idx(nstop), v[nstart]^v[nstop]))
		start=idx(nstart), stop=idx(nstop), ret=v[nstart]^v[nstop];
}

void func(int bit, int sa, int ea, int sb, int eb)
{
	if(sa>=eb)
		return;

	if(bit<0){
		for(int i=sa;i<ea;i++)
			tryupdate(i, std::lower_bound(sv+sb, sv+eb, make_pair(v[sb], idx(sa)))-sv);

		for(int i=sb;i<eb;i++)
			tryupdate(i, std::lower_bound(sv+sa, sv+ea, make_pair(v[sa], idx(sb)))-sv);
		return;
	}

	int num=1<<bit;

	int start=sa, end=ea;
	while(start<end){
		int mid=(start+end)/2;
		if(v[mid] & num)
			end=mid;
		else
			start=mid+1;
	}

	int p1=start;

	start=sb,end=eb;
	while(start<end){
		int mid=(start+end)/2;
		if(v[mid] & num)
			end=mid;
		else
			start=mid+1;
	}
	int p2=start;

	bool ok1=p1!=sa && p2!=eb;
	bool ok2=p1!=ea && p2!=sb;
	pair<int, int> p;

	if(ok1)
		func(bit-1,sa,p1,p2,eb);


	if(ok2)
		func(bit-1,p1,ea,sb,p2);

	if(!ok1 && !ok2){
		if(sa!=p1 && sb!=p2)
			func(bit-1,sa,p1,sb,p2);
		if(ea!=p1 && eb!=p2)
			func(bit-1,p1,ea,p2,eb);
	}
}

int main(void)
{
	freopen("xormax.in","r",stdin);
#ifdef INFOARENA
	freopen("xormax.out","w",stdout);
#endif

	int n;
	scanf("%d",&n);
	n++;

	for(int i=1;i<n;i++){
		scanf("%d",v+i);
		v[i]^=v[i-1];
		sv[i]=make_pair(v[i],i);
	}

	stop=1;
	ret=v[1];

	std::sort(sv,sv+n);
	for(int i=0;i<n;i++)
		v[i]=sv[i].first;

	func(21,0,n,0,n);
	if(start > stop)
		std::swap(start, stop);

	printf("%d %d %d\n", ret, start+1, stop);

	return 0;
	
}