Cod sursa(job #2238986)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 8 septembrie 2018 16:11:38
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>

using namespace std;

const int NMAX = 100000000;

int N,
    next[NMAX], C[NMAX], A[NMAX], B[NMAX], Co[NMAX];
char V[NMAX];

int compress(int x) {
    int r = x;
    while(next[r]) r = next[r];
    while(next[x]) {
        int aux = next[x];
        next[x] = r;
        x = aux;
    }
    return r;
}

inline int min(int a, int b) {
    return (a < b) ? a : b;
}

inline int max(int a, int b) {
    return (a < b) ? b : a;
}

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

    int a, b, c;
    scanf("%i %i %i %i", &N, &a, &b, &c);

    for(int i = 2; i <= N; i++) {
        A[i-1] = min(a, b);
        B[i-1] = max(a, b);
        Co[i-1] = c;

        a = (a*i)%N;
        b = (b*i)%N;
        c = (c*i)%N;
    }

    for(int i = N-1; i >= 1; i--) {
        int x = compress(A[i]);
        while(x <= B[i])
            if(V[x]) x = compress(x+1);
            else {
                V[x] = 1;
                C[x] = Co[i];
                next[x] = B[i]+1;
                x = compress(x+1);
            }
    }
    for(int i = 1; i < N; i++)
        printf("%i\n", C[i]);
    return 0;
}