Cod sursa(job #609780)

Utilizator cont_de_testeCont Teste cont_de_teste Data 23 august 2011 12:14:31
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>

long long n,a[1000010],b[1000010],c[1000010],r[1000010],v[1000010];

long long update(long long x,long long y) {
    if (r[r[x]]!=r[x]) {
        int rang = 0;
        for (rang = x; r[rang] != rang; rang = r[rang]);
        for (int aux; r[x] != x;) {
            aux = r[x];
            r[x] = rang;
            x = aux;
        }
        r[x] = rang;
        // r[x]=update(r[x],y);
    } else if (y) r[x]=y;
    return r[x];
}

int main() {
    long long i,j,aux;
    freopen("curcubeu.in","r",stdin);
    freopen("curcubeu.out","w",stdout);
    scanf("%lld%lld%lld%lld",&n,&a[1],&b[1],&c[1]);
    for (i=2; i<n; ++i) {
        a[i]=(a[i-1]*i)%n;
        b[i]=(b[i-1]*i)%n;
        c[i]=(c[i-1]*i)%n;
    }
    for (i=1; i<=n; ++i)
        r[i]=i;
    for (i=n-1; i>0; --i) {
        if (a[i]>b[i]) {
            aux=a[i];
            a[i]=b[i];
            b[i]=aux;
        }
        r[a[i]]=update(r[a[i]],0);
        for (j=r[a[i]]; j<=b[i]; j=r[j+1]) {
            v[j]=c[i];
            r[j+1]=update(r[j+1],0);
            r[j]=r[j+1];
        }
    }
    for (i=1; i<n; ++i)
        printf("%lld\n",v[i]);
    return 0;
}