Cod sursa(job #2238974)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 8 septembrie 2018 16:00:09
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>

using namespace std;

const int NMAX = 1000001;
struct col {
    int a, b, c;
};
col O[NMAX];
int N,
    next[NMAX], C[NMAX];
bool V[NMAX];

int compress(int x) {
    return (next[x] == 0) ? x : next[x] = compress(next[x]);
}

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

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

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++) {
        O[i-1].a = min(a, b);
        O[i-1].b = max(a, b);
        O[i-1].c = c;

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

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