Cod sursa(job #1942485)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 28 martie 2017 00:18:06
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 2200000
#define MaxL 100005
#define INF 2140000000
using namespace std;
  
FILE*IN,*OUT;

struct Trie
{
	int son0,son1;
}T[MaxN];
int N,Last[MaxN],DP[MaxL],Max=0,Start,End,Val,Size=0;
void New_Node(int x)
{
	T[x].son0=T[x].son1=0;
}
void Update(int x)
{
	int node=0;
	for(int i=20;i>=0;i--)
	{
		if((x&(1<<i))>0)
		{
			if(T[node].son1==0)
			{
				New_Node(++Size);
				T[node].son1=Size;
			}			
			node=T[node].son1;
		}
		else
		{
			if(T[node].son0==0)
			{
				New_Node(++Size);
				T[node].son0=Size;
			}			
			node=T[node].son0;
		}
	}
}
int Query(int x)
{
	int ans=0;
	int node=0;
	for(int i=20;i>=0;i--)
	{
		bool son=(x&(1<<i))>0;
		if(!son)
		{
			if(T[node].son1!=0)
				node=T[node].son1,ans+=1<<i;
			else node=T[node].son0;
		}
		else
		{
			if(T[node].son0!=0)
				node=T[node].son0;
			else node=T[node].son1,ans+=1<<i;
		}
	}
	return ans;
}
int main()
{
    IN=fopen("xormax.in","r");
    OUT=fopen("xormax.out","w");
	
	fscanf(IN,"%d",&N);

	for(int i=1;i<=N;i++)
	{
		fscanf(IN,"%d",&DP[i]);
		DP[i]^=DP[i-1];
	}
	New_Node(0);
	Update(0);
	for(int i=1;i<=N;i++)
	{
		Val=Query(DP[i]);
		if((DP[i]^Val)>Max)
			Max=(DP[i]^Val),End=i,Start=Last[Val]+1;
		Update(DP[i]);
		Last[DP[i]]=i;
	}
	fprintf(OUT,"%d %d %d",Max,Start,End);
	return 0;
}