Cod sursa(job #2393988)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 1 aprilie 2019 11:30:36
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 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;
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;
		v[i]=v[i-1]^x;
		if(v[i]>ma)
		{
			ma=v[i];
			poz=i;
			poz=i;
			poz2=i;
		}
	}
	sort(v+1,v+n+1);
	put=1;
	for(i=1; i<=21; i++)
	{
		put*=2;
	}
	for(i=0; i<=n; i++)
	{
		adauga(t,v[i],put);
	}
	for(i=0; i<=n; i++)
	{
		ma2=cauta(t,put,v[i]);
		if(ma<ma2)
        {
            r=1;
            ma=ma2;
            poz=v[i];
            poz2=v[i]^ma2;
		}
	}
	if(r==0)
    {
        //g<<ma<<" "<<poz<<" "<<poz2;
        return 0;
    }
    //g<<poz<<" "<<poz2<<'\n';
    f.close();
    f.open("xormax.in");
    f>>n;
	for(i=1; i<=n; i++)
	{
		f>>x;
		v[i]=v[i-1]^x;
		if(v[i]==poz)
        {
            poz3=i;
        }
        if(v[i]==poz2)
        {
            poz4=i;
        }
	}
	if(poz3>poz4)
    {
        swap(poz3,poz4);
    }
	g<<ma2<<" "<<poz3+1<<" "<<poz4;
	return 0;
}