Cod sursa(job #1395048)

Utilizator campionulFlavius Stoican campionul Data 20 martie 2015 23:05:53
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <cstdio>
#define nmax 1000005
using namespace std;
int n,a,b,c;
struct Coord{
 int x,y,c;
};
Coord d[nmax];
int urm[nmax],cul[nmax];
int main(){
    int i,j,st,dr,g;
    freopen("curcubeu.in","r",stdin);
    freopen("curcubeu.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
    d[1].x=min(a,b);d[1].y=max(a,b);d[1].c=c;
    urm[1]=2;
    for(i=2;i<n;i++){
        urm[i]=i+1;
        a=(a*i)%n;
        b=(b*i)%n;
        c=(c*i)%n;
        d[i].x=min(a,b);d[i].y=max(a,b);d[i].c=c;
    }
//    for(i=1;i<n;i++)
//        cout<<d[i].x<<' '<<d[i].y<<' '<<d[i].c<<'\n';
//    cout<<'\n';
    for(i=n-1;i>0;i--){
        st=d[i].x;
        dr=d[i].y;
        g=d[i].c;
        if(!cul[st])cul[st]=g;
        for(j=urm[st];j<=dr;j=urm[j]) if(!cul[j])cul[j]=g;
        urm[st]=max(urm[st],dr+1);
        urm[dr]=max(urm[dr],dr+1);
    }
    for(i=1;i<n;i++)
        cout<<cul[i]<<'\n';
    return 0;
}