Cod sursa(job #945389)

Utilizator Marius96Marius Gavrilescu Marius96 Data 1 mai 2013 20:30:59
Problema Xor Max Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 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;

bool isbetter(int ostart, int ostop, int nstart, int nstop)
{
	if(idx(nstop)<=idx(nstart))
		std::swap(nstop, nstart);
	if(idx(ostop)<=idx(ostart))
		std::swap(ostop, ostart);

	if((v[nstart]^v[nstop]) > (v[ostart]^v[ostop]))
		return 1;
	if((v[nstart]^v[nstop]) < (v[ostart]^v[ostop]))
		return 0;

	if(idx(nstop)<idx(ostop))
		return 1;
	if(idx(nstop)>idx(ostop))
		return 0;

	return idx(nstart) > idx(ostart);
}

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

	if(bit<0){
		if(isbetter(start, stop, sa, sb))
			start=sa, stop=sb;
		if(isbetter(start, stop, sa, eb-1))
			start=sa, stop=eb-1;
		if(isbetter(start, stop, ea-1, sb))
			start=ea-1, stop=sb;
		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);
	}

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

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

	printf("%d %d %d\n", v[start]^v[stop], idx(start)+1, idx(stop));

	return 0;
	
}