Cod sursa(job #1205317)

Utilizator catalinrebegeaUNIBUC-Claudia Catarig catalinrebegea Data 5 iulie 2014 22:48:51
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#define Nmax 1000005

using namespace std;

int cul[Nmax],A[Nmax],B[Nmax],C[Nmax],nxt[Nmax];

inline int Find(int p)
{
    int i=p,rad,aux;
    while(cul[p])
        p=nxt[p];
    rad=p;
    while(cul[i])
    {
        aux=nxt[i];
        nxt[i]=rad;
        i=aux;
    }
    return rad;
}

int main()
{
    int N,i,j,aux;
    freopen ("curcubeu.in","r",stdin);
    freopen ("curcubeu.out","w",stdout);
    scanf("%d%d%d%d", &N,&A[1],&B[1],&C[1]);
    --N;
    for(i=2;i<=N;++i)
    {
        A[i] = (1LL*A[i-1] * i) % (N+1);
        B[i] = (1LL*B[i-1] * i) % (N+1);
        C[i] = (1LL*C[i-1] * i) % (N+1);
    }
    for(j=N;j;--j)
    {
        if(B[j]<A[j])
        {
            aux=A[j]; A[j]=B[j]; B[j]=aux;
        }
        for(i=A[j];i<=B[j];)
            if(!cul[i])
            {
                cul[i]=C[j];
                nxt[i++]=Find(B[j]+1);
            }
            else
                i=Find(i);
    }
    for(i=1;i<=N;++i)
        printf("%d\n", cul[i]);
    return 0;
}