Cod sursa(job #86620)

Utilizator goguGogu Marian gogu Data 25 septembrie 2007 01:24:57
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#define MaxN 1000100
#define MaxR (3*MaxN)
#define LIM 1

unsigned n, a, b, c, st, fn;
int cul[MaxN], A[MaxR];
char full[MaxR];

void update(unsigned p, unsigned u, unsigned r)
{
     if (u-p < LIM){
        if (p<st) p=st;
        if (u>fn) u=fn;
        while (p <= u) A[p++] = c;
        return;
     }
     if (st<=p && u<=fn){
        full[r] = 1;
        cul[r] = c;
        return;
     }
     full[r] = 0;
     unsigned mij = (p+u)/2;
     if (st<=mij) update(p, mij, 2*r);
     if (fn > mij)update(mij+1, u, 2*r+1);
}

void afis(unsigned p, unsigned u, unsigned r)
{
     if (u-p < LIM){
        while (p <= u) printf("%u\n", A[p++]);
        return;
     }
     if (full[r]){
        while (p <= u) ++p, printf("%u\n", cul[r]);
        return;
     }
     unsigned mij = (p+u)/2;
     afis(p, mij, 2*r);
     afis(mij+1, u, 2*r+1);
}

int main()
{
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);
    scanf("%u %u %u %u", &n, &a, &b, &c);
    full[1] = 1;
    for (unsigned i=2; i<=n; i++){
        if (a<b) st=a, fn=b; else st=b, fn=a;
        if (!st) st++;
        update(1, n-1, 1);
        a = ((unsigned long long) a * i) % n;
        b = ((unsigned long long) b * i) % n;
        c = ((unsigned long long) c * i) % n;
    }
    afis(1, n-1, 1);
    return 0;
}