Cod sursa(job #1806958)

Utilizator penetavyPene Cosmin-Octavian penetavy Data 15 noiembrie 2016 21:01:40
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <stdio.h>

#define N_MAX 1000000

using namespace std;

FILE *fin = fopen("curcubeu.in", "r");
FILE *fout = fopen("curcubeu.out", "w");

int N, A, B, C;
int mic, mare;

int colour[N_MAX + 1];
int boss[N_MAX + 1];

int find(int x) {
    int t;
    if(x == boss[x])
        return x;
    else {
        t = find(boss[x]);
        if (t != 0)
            boss[x] = t;
        return t;
    }
}

struct anakin {
    int inc, sf, color;
};

anakin pas[N_MAX + 1];

void init() {
    int i;
    for (i = 1; i <= N - 1; i++)
        boss[i] = i - 1;
}

int main(){
    int i, j;
    int t;
    int ver;

    fscanf(fin, "%d %d %d %d", &N, &A, &B, &C);

    init();

    for (t = 1; t <= N - 1; t++) {
        if (A > B) {
            mic = B;
            mare = A;
        }
        else {
            mic = A;
            mare = B;
        }

//        fprintf(fout, "%d %d %d\n", mic, mare, C);

        pas[t].inc = mic;
        pas[t].sf = mare;
        pas[t].color = C;

        A = (1LL * A * (t + 1)) % N;
        B = (1LL * B * (t + 1)) % N;
        C = (1LL * C * (t + 1)) % N;
    }

//    for (i = 1; i <= N - 1; i++)
//        printf("%d %d\n", i, boss[i]);

    for (i = N - 1; i >= 1; i--) {
        mic = pas[i].inc;
        mare = pas[i].sf;
        C = pas[i].color;
        ver = 1;
        while (mic <= mare && find(mic) != 0)
            mic++;
        while (mic <= mare && find(mare) != 0)
            mare--;
        if (mic <= mare) {
            colour[mic] = C;
            if(boss[mare + 1] == mare)
                boss[mare + 1] = boss[mic];
            boss[mic] = mic;
        }
    }

//    for (i = 1; i <= N - 1; i++)
//        printf("%d %d\n", i, boss[i]);

    for (i = 1; i <= N - 1; i++)
        fprintf(fout, "%d\n", colour[find(i)]);

    fclose(fin);
    fclose(fout);
    return 0;
}