Cod sursa(job #2394072)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 1 aprilie 2019 12:01:25
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n,i,x,v[100010],put,x2,y2,ma,ma2,poz,poz2,poz3,poz4,r,nr[100009];
struct Trie
{
	Trie *fii[2];
};
Trie *t=new Trie();
void adauga(Trie *p,int x,int put)
{
	if(put==0)
	{
		return;
	}
	if(i==1)
	{
		//g<<x<<" "<<put<<" "<<x/put%2<<'\n';
	}
	if(p->fii[(x/put)%2]==NULL)
	{
		p->fii[(x/put)%2]=new Trie();
	}
	adauga(p->fii[(x/put)%2],x%put,put/2);
}
int cauta(Trie *p,int put,int x)
{
	//g<<put<<'\n';
	if(put==0)
	{
		return 0;
	}
	if(p->fii[(x/put)^1]!=NULL)
	{
		return put+cauta(p->fii[(x/put)^1],put/2,x%put);
	}
	else
	{
		return cauta(p->fii[(x/put)],put/2,x%put);
	}
}
int main()
{
	f>>n;
	for(i=1; i<=n; i++)
	{
		f>>x;
		nr[i]=x;
		v[i]=v[i-1]^x;
		if(v[i]>ma)
		{
			ma=v[i];
			poz=i;
			poz=i;
			poz2=i;
		}
	}
	put=1;
	for(i=1; i<=21; i++)
	{
		put*=2;
	}/*
	for(i=0; i<=n; i++)
	{
		adauga(t,v[i],put);
	}*/
	adauga(t,0,put);
	for(i=1; i<=n; i++)
	{
		ma2=cauta(t,put,v[i]);
		if(ma<ma2)
		{
			r=1;
			ma=ma2;
			poz=v[i];
			poz2=v[i]^ma2;
			poz4=i;
		}
		adauga(t,v[i],put);
	}
	if(r==0)
	{
		//g<<ma<<" "<<poz<<" "<<poz2;
		return 0;
	}
	//g<<poz<<" "<<poz2<<'\n';
	f.close();
	//f.open("xormax.in");
	//f>>n;
	long long xoor=0;
	for(i=poz4; i>0; --i)
	{
	    xoor^nr[i];
	    if (xoor==ma)
        {
            poz3=i;
            break;
        }
	}
	g<<ma<<" "<<poz3+1<<" "<<poz4;
	return 0;
}