Cod sursa(job #1451731)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 18 iunie 2015 12:08:23
Problema Curcubeu Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <stdio.h>
#define MAXN 1000000
int a[MAXN], b[MAXN], c[MAXN], v[MAXN+1], t[MAXN], min[MAXN], max[MAXN];
int find(int x){
    if(t[x]==x){
        return x;
    }
    t[x]=find(t[x]);
    return t[x];
}
inline void unite(int x, int y){
    int rx=find(x), ry=find(y);
    if(min[rx]<min[ry]){
        min[ry]=min[rx];
    }
    if(max[rx]>max[ry]){
        max[ry]=max[rx];
    }
    t[rx]=ry;
}
int main(){
    int n, i, aux, x;
    long long p;
    FILE *fin, *fout;
    fin=fopen("curcubeu.in", "r");
    fout=fopen("curcubeu.out", "w");
    fscanf(fin, "%lld%d%d%d", &p, &a[1], &b[1], &c[1]);
    n=p-1;
    for(i=2; i<=n; i++){
        a[i]=(1LL*a[i-1]*i)%p;
        b[i]=(1LL*b[i-1]*i)%p;
        c[i]=(1LL*c[i-1]*i)%p;
    }
    for(i=1; i<=n; i++){
        t[i]=min[i]=max[i]=i;
        v[i]=0;
    }
    v[0]=v[n+1]=0;
    for(i=n; i>0; i--){
        if(a[i]>b[i]){
            aux=a[i];
            a[i]=b[i];
            b[i]=aux;
        }
        x=a[i];
        while(x<=b[i]){
            if(v[x]==0){
                v[x]=c[i];
            }
            if(v[x-1]!=0){
                unite(x, x-1);
            }
            if(v[x+1]!=0){
                unite(x, x+1);
            }
            x=max[find(x)]+1;
        }
    }
    for(i=1; i<=n; i++){
        fprintf(fout, "%d\n", v[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}