Cod sursa(job #182737)

Utilizator DorinOltean Dorin Dorin Data 21 aprilie 2008 11:48:13
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 kb
# include <stdio.h>
//# include <string.h>
# include <vector>

using namespace std;

# define input "xormax.in"
# define output "xormax.out"

struct trie
{
   int bit0,bit1,nod;
   trie * urm0;
   trie * urm1;
}*cap;

# define mbit 22

int rez,i,j,n,temp,ant;
int st,dr;

void init(trie * e)
{
	e->bit0 = 0;
	e->bit1 = 0;
}

void cherche(int x)
{
	if(x > rez)
	{
		rez = x;
		st = 1;dr = i;
    }
	 int biti[32],res[32];
	 memset(biti,0,sizeof(biti));
	 memset(res,0,sizeof(biti));
     int nrbiti = 0;
     while(x)
     {
        biti[nrbiti++] = x&1;
        x>>=1;
	 }
	 nrbiti = mbit;
     j = nrbiti;
	 trie * aux = cap;
	 
 	 int st1 = i;
	 if(cap)
	 if(cap->bit0 || cap->bit1)
	 while(j >= 0)
     {
         if(biti[j])
         {
             if(cap->bit0)
             {
                res[j] = 1;
                st1=cap->nod;
                cap = cap->urm0;
             }
             else
             {
                 res[j] = 0;
                 st1=cap->nod;
                 cap = cap->urm1;
             }
         }
         else
         {
             if(cap->bit1)
             {
                res[j] = 1;
                st1=cap->nod;
                cap = cap->urm1;
             }
             else
             {
                 res[j] = 0;
                 st1 = cap->nod;
                 cap = cap->urm0;
             }
         }
         j--;
     }
     cap = aux;
	 j = 0;
     temp = 0;
	 while(j <= nrbiti)
	 {
		if(res[j])
		   temp += 1<<j;
       j++;
	 }
	 if(temp > rez)
	 {
			 rez = temp;
			 dr=i;
			 st = st1+1;
	 }
	 if(temp == rez && i == dr && st < st1+1)
       st = st1+1;
	 while(nrbiti >= 0)
	 {
		if(biti[nrbiti])
		{
            
            if(aux && aux->bit1)
               aux = aux->urm1;
            else
            {
				trie * xx = new trie;
				init(xx);
                aux->bit1 = 1;
                aux->nod = i;
                aux->urm1 = xx;
                aux = xx;
            }

        }
        else
        {
            if(aux && aux->bit0)
                aux = aux->urm0;
            else
			{
				trie * xx = new trie;
				init(xx);
                aux->bit0 = 1;
                aux->nod = i;
                aux->urm0 = xx;
                aux = xx;
            }
        }
        nrbiti--;        
     }
     
}

int main()
{
    freopen(input, "r", stdin );
    freopen(output, "w", stdout );
    
	scanf("%d",&n);

    int x;
    cap = new trie;
    init(cap);
    ant = 0;
    for(i=1;i<=n;i++)
    {
       scanf("%d",&x);
       if(x > rez)
       {
            rez = x;
            st = dr = i;
       }
       ant = ant ^ x;
       cherche(ant);
    }
       
    printf("%d %d %d",rez,st,dr);
                    
    return 0;
}