Cod sursa(job #2261443)

Utilizator BlatTraditionalBlat Traditional BlatTraditional Data 16 octombrie 2018 11:13:34
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda nu_poate_veni_deci_nu_e_shimulare Marime 1.56 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] = {min(a, b), max(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 = 1; i <= n; i++)
        nextUncolored[i] = i + 1;
    for (int i = 1; i < n; i++) {
        int pos = updates[i].left;
        while (pos <= updates[i].right) {
            while (pos <= updates[i].right && color[pos])
                pos = nextUncolored[pos];
            if (pos > updates[i].right)
                break;
            pos = nextUncolored[pos];
        }
        int pos1 = updates[i].left;
        while (pos1 <= updates[i].right) {
            while (pos1 <= updates[i].right && color[pos1])
                pos1 = nextUncolored[pos1];
            if (pos1 > updates[i].right)
                break;
            color[pos1] = updates[i].col;
            int aux = nextUncolored[pos1];
            nextUncolored[pos1] = pos;
            pos1 = aux;
        }
    }
    for (int i = 1; i <= n - 1; i++)
        out << color[i] << "\n";
    return 0;
}