Cod sursa(job #132212)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 5 februarie 2008 13:12:33
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
//xormax
#include<stdio.h>
FILE*fin=fopen("xormax.in","r");
FILE*fout=fopen("xormax.out","w");
#define maxc 20
#define maxn 100001
struct nod{struct nod * st, * dr;};
typedef struct nod*trie;
int n,a[maxn][maxc+1],sumx[maxn][maxc+1];
void to2(int nr,int w[])
{
  int i;
  for(i=maxc;i>=0;i--)
    if(nr&(1<<i)) w[i]=1;
    else w[i]=0;
}
int to10(int w[])
{
  int i,nr=0;
  for(i=0;i<=maxc;i++)
    if(w[i]==1) nr+=(1<<i);
  return nr;
}

void sxor(int w[],int y[],int t[])
{
  int i;
  for(i=0;i<=maxc;i++)
    t[i]=w[i]^y[i];
}

int main()
{
  int i,j,nr,best=-1,g,b[maxc+1],bb[maxc+1],p;
  trie prim,ultim,nn;
  fscanf(fin,"%d",&n);

  for(i=0;i<=maxc;i++)
    sumx[0][i]=0;

  prim=new nod;ultim=prim;
  for(i=0;i<=maxc;i++)
  {
    nn=new nod;
    ultim->st=nn;
    ultim->dr=NULL;
    ultim=nn;
  }
  ultim->st=NULL;ultim->dr=NULL;
  for(i=1;i<=n;i++)
  {
    fscanf(fin,"%d",&nr);
    to2(nr,a[i]);
    sxor(a[i],sumx[i-1],sumx[i]);
    ultim=prim;
    for(j=maxc;j>=0;j--)
      if(sumx[i][j]==1) if(!(ultim->dr)){nn=new nod;ultim->dr=nn;nn->st=NULL;nn->dr=NULL;ultim=nn;}
			else ultim=ultim->dr;
      else if(!(ultim->st)){nn=new nod;ultim->st=nn;nn->st=NULL;nn->dr=NULL;ultim=nn;}
	   else ultim=ultim->st;
    ultim=prim;
    for(j=maxc;j>=0;j--)
      if(sumx[i][j]==1) if(ultim->st){b[j]=1;ultim=ultim->st;}
			else{b[j]=0;ultim=ultim->dr;}
      else if(ultim->dr){b[j]=1;ultim=ultim->dr;}
	   else{b[j]=0;ultim=ultim->st;}
    nr=to10(b);
    if(nr>best)
    {
      best=nr;
      for(j=0;j<=maxc;j++)
	bb[j]=b[j]^sumx[i][j];
      p=i;
    }
  }
  for(j=p-1;j>=0;j--)
  {
    g=1;
    for(i=0;i<=maxc;i++)
      if(sumx[j][i]!=bb[i]){g=0;break;}
    if(g==1){i=j+1;break;}
  }
  fprintf(fout,"%d%c%d%c%d%c",best,' ',i,' ',p,'\n');
  fclose(fin);
  fclose(fout);
  return 0;
}