Cod sursa(job #2298026)

Utilizator iulius510iulius alexandru iulius510 Data 6 decembrie 2018 23:19:07
Problema Xor Max Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<fstream>
#include<string>
#include<set>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n,a[100001],valmax,incmax,sfmax,x;
class Trie
{ public:
 Trie *fii[2];
 int val;
 set<int>elem;
  
  Trie()
    {val=0;
	 for(int i=0;i<=1;i++)
	 	fii[i]=0;
    }
    int element(int x)
    {
    	set<int>::iterator t;
    	t=elem.lower_bound(x);
    	return *t;
    }
	
}*rad=new Trie();
void ad_number(int x,Trie *q,const int n,const int indice)
{  
	if(x==-1)
	{   q->val=n;
       (q->elem).insert(indice); 
		return;
	}
	if(q->fii[!!(n&(1<<x))]==0) // s ar putea sa apara probleme aici;
	 q->fii[!!(n&(1<<x))]=new Trie();
	ad_number(x-1,q->fii[!!(n&(1<<x))],n,indice);
}
int * find_sol(int n,int el,Trie *q,int x)
{
	if(x==-1)
	{
      static int v[2];
      v[0]=(n^(q->val));
      v[1]=q->element(el);
      return v;
	}
	if(q->fii[!(n&(1<<x))]!=0)
		return find_sol(n,el,q->fii[!(n&(1<<x))],x-1);
	 return find_sol(n,el,q->fii[!!(n&(1<<x))],x-1);
}
int main()
{
    f>>n;
    f>>a[1];
    valmax=a[1];
    incmax=1;
    sfmax=1;
    for(int i=2;i<=n;i++)
    {
    	f>>x;
    	a[i]=(x^a[i-1]);
    	ad_number(21,rad,a[i],i);
    }
    for(int i=1;i<=n-1;i++)
    {
    	int *v;
    	v=find_sol(a[i],i,rad,21);
    	if(v[0]>valmax)
    	{
    		incmax=i+1;
    		sfmax=v[1];
    		valmax=v[0];
    	}
    	else if(v[0]==valmax)
    		  {
    		  	if(v[1]>sfmax)
    		  	{
    		  		sfmax=v[1];
    		  		incmax=i+1;
    		  	}
    		  	else if(v[1]==sfmax)
    		  		  {
    		  		  	if((v[1]-i+1)<(sfmax-incmax))
    		  		  	{
    		  		  		sfmax=v[1];
    		  		  		incmax=i+1;
    		  		  	}
    		  		  }
    		  }
    }
    if(a[n]>valmax)
    	{sfmax=n;
    	 valmax=a[n];
    	 incmax=1;
    	}
    else if(a[n]==valmax)
    	  {
    	  	if(sfmax<n)
    	  	{
    	  		sfmax=n;
    	  		incmax=1;
    	  	}
    	  }
    g<<valmax<<' '<<incmax<<' '<<sfmax;
	return 0;
}