Cod sursa(job #945371)

Utilizator Marius96Marius Gavrilescu Marius96 Data 1 mai 2013 19:27:32
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<cstdio>

#include<algorithm>

#define apply(bit, sa, ea, sb, eb) do { p=func(bit, sa, ea, sb, eb);	\
	int old=v[r1]^v[r2],now=v[p.first] ^ v[p.second];					\
	if(now>old || (now==old && (sv[r2].second>sv[p.second].second || (sv[r2].second==sv[p.second].second && sv[r1].second<sv[p.first].second)))) r1=p.first, r2=p.second; } while(0)

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

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

pair<int, int> func(int bit, int sa, int ea, int sb, int eb)
{
	if(sb<ea && sa>eb)
		return make_pair(0,0);
	if(ea-sa == 1 && eb-sb == 1)
		return make_pair(sa, sb);
	if(bit==1)
		return make_pair(sa, eb-1);

	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;

	int r1=0,r2=0;

	if(bit>0){
		bool ok1=p1!=sa && p2!=eb;
		bool ok2=p1!=ea && p2!=sb;
		pair<int, int> p;

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


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

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

	return make_pair(r1,r2);
}

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

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

	int a=1,b=1,mxn=v[0];
	for(int i=1;i<n;i++){
		scanf("%d",v+i);

		v[i]^=v[i-1];

		sv[i]=make_pair(v[i],i+1);
	}

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

	pair<int, int> p=func(21,0,n,0,n);
	if(sv[p.first].second > sv[p.second].second)
		std::swap(p.first, p.second);

	if(mxn <= (v[p.first] ^ v[p.second]))
		printf("%d %d %d\n", v[p.first]^v[p.second], sv[p.first].second+1, sv[p.second].second);
	else
		printf("%d %d %d\n", mxn, a, b);

	return 0;
	
}