Cod sursa(job #1452516)

Utilizator atatomirTatomir Alex atatomir Data 21 iunie 2015 11:23:06
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <cstdio>

using namespace std;

#define mp make_pair
#define F first
#define S second
#define maxN (1<<20)

long n,i,_n;
pair< long , pair<long,long> > Q[maxN];
long a,b,c;
long col[maxN];
long wh [maxN];

void solve(long s,long d,long what){
    long _fin=d+1,_s;
    //while(col[_fin]) _fin = wh[_fin];
    while(s<=d){
        if(!col[s]) col[s] = what;
        _s = s;
        s = wh[s];
        wh[_s] = _fin;
    }
}

int main()
{
    freopen("curcubeu.in","r",stdin);
    freopen("curcubeu.out","w",stdout);

    scanf("%ld %ld %ld %ld",&n,&Q[1].S.F,&Q[1].S.S,&Q[1].F);
    _n = n;

    for(i=2;i<n;i++){
        Q[i].F = (1LL*Q[i-1].F*i)%n;
        Q[i].S.F = (1LL*Q[i-1].S.F*i)%n;
        Q[i].S.S = (1LL*Q[i-1].S.S*i)%n;
    }

    for(i=1;i<n;i++) wh[i] = i+1;

    for(;--n>0;){
        a = Q[n].S.F;
        b = Q[n].S.S;
        c = Q[n].F;
        if(a>b) swap(a,b);

        solve(a,b,c);
    }

    n = _n;
    for(i=1;i<n;i++) printf("%ld\n",col[i]);

    return 0;
}