Cod sursa(job #87768)

Utilizator sealTudose Vlad seal Data 28 septembrie 2007 23:11:26
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#define Nm (1<<20)
#define min(a,b) ((a)<(b)?(a):(b))
int A[Nm],B[Nm],C[Nm],T[Nm],Ans[Nm];

int find_compress(int a)
{
    int r=a,x;
    while(T[r])
        r=T[r];
    while(T[a])
    {
        x=T[a];
        T[a]=r;
        a=x;
    }
    return r;
}

int main()
{
    int n,a,b,i,j,k;

    freopen("curcubeu.in","r",stdin);
    scanf("%d%d%d%d",&n,A+1,B+1,C+1);
    
    for(i=2;i<n;++i)
    {
        A[i]=(long long)A[i-1]*i%n;
        B[i]=(long long)B[i-1]*i%n;
        C[i]=(long long)C[i-1]*i%n;
    }

    for(i=n-1;i;--i)
    {
        a=min(A[i],B[i]); b=A[i]+B[i]-a;
        j=find_compress(a);
        while(j<=b)
        {
            Ans[j]=C[i];
            k=find_compress(j+1);
            T[j]=k; j=k;
        }
    }

    freopen("curcubeu.out","w",stdout);
    for(i=1;i<n;++i)
        printf("%d\n",Ans[i]);
    return 0;
}