Cod sursa(job #2261363)

Utilizator BlatTraditionalBlat Traditional BlatTraditional Data 16 octombrie 2018 10:31:22
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda nu_poate_veni_deci_nu_e_shimulare Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("curcubeu.in");
ofstream out("curcubeu.out");

const int MAX_N = 1000000;

struct Update {
    int left;
    int right;
    int col;
};

Update updates[1 + MAX_N];
int nextUncolored[1 + MAX_N];
int color[1 + MAX_N];

int main() {
    int n, a, b, c;
    in >> n >> a >> b >> c;
    updates[1] = {a, b, c};
    for (int i = 2; i <= n - 1; i++) {
        a = (1LL * a * i) % n;
        b = (1LL * b * i) % n;
        c = (1LL * c * i) % n;
        updates[i] = {min(a, b), max(a, b), c};
    }
    reverse(updates + 1, updates + n - 1 + 1);
    for (int i = 0; i <= n; i++)
        nextUncolored[i] = i + 1;
    for (int i = 1; i < n; i++) {
        int pos = updates[i].left - 1;
        while (pos <= n && nextUncolored[pos] <= updates[i].right) {
            pos = nextUncolored[pos];
            color[pos] = updates[i].col;
            nextUncolored[pos] = nextUncolored[updates[i].right];
        }
        nextUncolored[updates[i].left - 1] = nextUncolored[updates[i].right];
    }
    for (int i = 1; i <= n - 1; i++)
        out << color[i] << "\n";
    return 0;
}