Cod sursa(job #235630)

Utilizator katakunaCazacu Alexandru katakuna Data 24 decembrie 2008 19:36:15
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<stdio.h>

int A[1000111],B[1000111],C[1000111],ta,r,x,jj,t[1000111],n,a,b,c,cu[1000111],i,j;


int main(){

FILE *f=fopen("curcubeu.in","r");
fscanf(f,"%d %d %d %d",&n,&A[1],&B[1],&C[1]);
fclose(f);

int ok=1;

   for(i=2;i<=n;i++){
   t[i]=1;
   }

t[1]=-(n-1);
cu[n]=0;

   for(i=2;i<n;i++){
   A[i]=(long long)((long long)A[i-1]*(long long)i)%n;
   B[i]=(long long)((long long)B[i-1]*(long long)i)%n;
   C[i]=(long long)((long long)C[i-1]*(long long)i)%n;
   }

int aux,nr=0;

  for(i=n-1;i;i--){
  a=A[i];
  b=B[i];
  c=C[i];

   if(b<a){
   aux=b;
   b=a;
   a=aux;
   }

    if(t[a] < 0)
    ta=a;
    else
    ta=t[a];

      if( !cu[ta] ){
  //  t[ta]=-1;
      t[a]=-1;
      
         if(a!=ta)
         t[ta]=-(a-ta);
      cu[a]=c;
      nr++;
      r=a;
      x=a+1;
      }


      else{
      r=ta;
      x=ta+(-t[ta]);

        while(cu[x]){
        ta=x;
        x=ta+(-t[ta]);
        }

      }
      
         while(x<=b && !cu[x]){
         cu[x]=c;
         nr++;
         t[r]--;
         t[x]=r;
         x++;

            while(t[x] < 0 && cu[x]){
            r=x;
            x=x+(-t[x]);
            }
         }

         if(x==b+1 && ! cu[x]){
         r=x;
         t[x]=-1;
         x++;

            for(;t[x] > 0;x++){
            t[x]=r;
            t[r]--;
            }
            
            
         }
  }

FILE *g=fopen("curcubeu.out","w");
  for(i=1;i<n;i++)
  fprintf(g,"%d\n",cu[i]);
fclose(g);

return 0;
}