Cod sursa(job #2129)

Utilizator stef2nStefan Istrate stef2n Data 16 decembrie 2006 05:26:27
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <stdio.h>

#define infile "xormax.in"
#define outfile "xormax.out"
#define NMAX 100005
#define MAX_LEVEL 21

unsigned int mask[]={1048576,524288,262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1};

struct TRIE
      {
       char niv;
       unsigned int val;
       TRIE *st,*dr;
       unsigned int end;
      };

TRIE *prim;

inline void adauga(TRIE *(&prim), char niv, unsigned int val, unsigned int end)
  {
   if(!prim)
     {
      prim=new TRIE;
      prim->niv=niv;
      prim->st=prim->dr=NULL;
      prim->val=val;
      prim->end=end;
     }
   if(niv!=MAX_LEVEL)
     if(mask[niv]&val)
       adauga(prim->dr,niv+1,val,end);
     else
       adauga(prim->st,niv+1,val,end);
   else
     if(end>prim->end)
       prim->end=end;
  }

inline void cauta(TRIE *prim, unsigned int val, unsigned int &c_m_a_val, unsigned int &end)
  {
   if(prim->niv==MAX_LEVEL)
     {
      c_m_a_val=prim->val;
      end=prim->end;
      return;
     }
   if(mask[prim->niv]&val)
     if(prim->dr)
        cauta(prim->dr,val,c_m_a_val,end);
     else
        cauta(prim->st,val,c_m_a_val,end);
   else
     if(prim->st)
        cauta(prim->st,val,c_m_a_val,end);
     else
        cauta(prim->dr,val,c_m_a_val,end);
  }

FILE *fin,*fout;
unsigned int n,suma[NMAX],maxim=0,start=0,end=1;

void citire()
  {
   unsigned int i,val;
   fin=fopen(infile,"r");
   fscanf(fin,"%d",&n);
   suma[0]=0;
   for(i=1;i<=n;i++)
      {
       fscanf(fin,"%u",&val);
       suma[i]=(suma[i-1]^val);
      }
   fclose(fin);
  }

void solutie()
  {
   unsigned int c_m_a_val,start_poz;

   prim=NULL;
   adauga(prim,0,0,0);
   for(unsigned int i=1;i<=n;i++)
      {
       cauta(prim,(~suma[i]),c_m_a_val,start_poz);
       if((unsigned int)(suma[i] ^ c_m_a_val) > (unsigned int)maxim)
         {maxim=(suma[i]^c_m_a_val);
          start=start_poz;
          end=i;}
       adauga(prim,0,suma[i],i);
      }
  }


int main()
{
citire();
solutie();
fout=fopen(outfile,"w");
fprintf(fout,"%u %u %u\n",maxim,start+1,end);
fclose(fout);
return 0;
}