Cod sursa(job #349061)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 17 septembrie 2009 21:16:40
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
# include <stdio.h>
# include <stdlib.h>

typedef struct INTERVAL
        {
        long int a,b,c;
        };
        
const long int MAXN=1000000;

INTERVAL interval[MAXN+1];
long int n,col[MAXN+1],set[MAXN+1],size[MAXN+1];
        
void citire()
{
     long int a,c,b;
     FILE *f=fopen("curcubeu.in","r");
     fscanf(f,"%ld%ld%ld%ld",&n,&a,&b,&c);
     long int i=1;
     do
       {
       if (a<b) 
          {
          interval[i].a=a;
          interval[i].b=b;
          }
       else
           {
           interval[i].b=a;
           interval[i].a=b;
           }
       interval[i].c=c;
       i++;
       a=(a*i)%n;
       b=(b*i)%n;
       c=(c*i)%n;
       }
     while (i<=n-1);
}      

long int get_set(long int j)
{
     long int i=j;
     while (set[i]!=i) i=set[i];
     set[j]=i;
     return i;
}

long int merge_set(long int a, long int b)
{
     if (a<b) 
        {
        set[b]=a;
        size[a]+=size[b];
        }
     else
         {
         set[a]=b;
         size[b]+=size[a];
         }
}

void paint(long int a, long int b, long int c)
{
     long int i,pr,act;
     for (i=a;i<=b;)
         if (col[i]==0) 
            {
            col[i]=c;
            if (i>1) 
               {
               pr=get_set(i-1);
               set[i]=pr;size[pr]++;
               }
            i++;
            }
         else
            {
            if (i>a) 
               {
               pr=get_set(i-1);
               act=get_set(i);
               if (pr!=act) 
                  {
                  set[act]=pr;
                  size[pr]+=size[act];
                  i=pr+size[pr];
                  }
               i=pr+size[pr];
               }
            else
               {
               pr=get_set(i);
               i=pr+size[pr];
               }
            }
}

void calculeaza()
{
     long int i;
     for (i=1;i<=n-1;i++) {set[i]=i;size[i]=1;}
     for (i=n-1;i>=1;i--)
         paint(interval[i].a,interval[i].b,interval[i].c);
}

void scrie()
{
     FILE *g=fopen("curcubeu.out","w");
     long int i;
     for (i=1;i<=n-1;i++)
         fprintf(g,"%ld\n",col[i]);
     fclose(g);
}

int main()
{
    citire();
    calculeaza();
    scrie();
    return 0;
}