Cod sursa(job #2470014)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 8 octombrie 2019 16:55:09
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <cstring>
#include <iostream>
 
using namespace std;
ifstream fi("xormax.in");
ofstream fo("xormax.out");
const int NMAX=1e5+5;
int n,s[NMAX],lg,maxim,sol=-1,curr,st,solst,soldr;
struct Trie
{
	Trie *fii[2];
	int start;
	Trie() {
		memset(fii,0,sizeof(fii));
        start=0;
	}
};
Trie *root=new Trie();
void inserare(Trie *nod, int pos, int ind)
{
	bool bit=(1<<(lg-pos-1))&s[ind];
	if(pos!=lg)
	{
		if(!(nod->fii[bit]))
			nod->fii[bit]=new Trie();
		inserare(nod->fii[bit],pos+1,ind);
	}
	else nod->start=ind;
}
int compar(Trie *nod, int pos, int ind)
{
	bool bit=(1<<(lg-pos-1))&s[ind];
	if(pos!=lg)
	{
		if(nod->fii[1-bit])
		{
			curr+=(1<<(lg-pos-1));
			compar(nod->fii[1-bit],pos+1,ind);
		}
        else compar(nod->fii[bit],pos+1,ind);
	}
	else return nod->start;
}
int main()
{
	fi>>n;
	for(int i=1;i<=n;i++)
	{
		fi>>s[i];
		s[i]^=s[i-1];
		maxim=max(s[i],maxim);
	}
	for(lg=0;(1<<lg)<=maxim;lg++);
	inserare(root,0,0);
	for(int i=1;i<=n;i++)
	{
		if(s[i]>sol)
		{
			sol=s[i];
			solst=1;
			soldr=i;
		}
		curr=0;
		st=compar(root,0,i);
		if(curr>sol)
		{
			sol=curr;
			solst=st+1;
			soldr=i;
		}
		inserare(root,0,i);
	}
	fo<<sol<<" "<<solst<<" "<<soldr<<"\n";
	fi.close();
	fo.close();
	return 0;
}