Cod sursa(job #1612935)

Utilizator BrandonChris Luntraru Brandon Data 25 februarie 2016 09:23:07
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>

#define MAXSIZE 1000005

using namespace std;

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

int n, nxt[MAXSIZE], clr[MAXSIZE];
long long a[MAXSIZE], b[MAXSIZE], c[MAXSIZE];

void read() {
    cin >> n >> a[1] >> b[1] >> c[1];
    for(int i = 2; i <= n; ++i) {
        a[i] = (a[i - 1] * (long long) i) % n;
        b[i] = (b[i - 1] * (long long) i) % n;
        c[i] = (c[i - 1] * (long long) i) % n;
    }
}

int find_nxt(int pos) {
    if(pos == nxt[pos]) {
        return pos;
    }

    return nxt[pos] = find_nxt(nxt[pos]);
}

void solve() {
    for(int i = 1; i <= n; ++i) {
        nxt[i] = i;
    }

    for(int i = n; i >= 1; --i) {
        int l = min(a[i], b[i]);
        int r = max(a[i], b[i]);
        l = find_nxt(l);

        for(int j = l; j <= r; ++j) {
            if(clr[j]) {
                j = find_nxt(j);
                continue;
            }

            clr[j] = c[i];
        }

        nxt[l] = find_nxt(r + 1);
    }
}

void print() {
    for(int i = 1; i < n; ++i) {
        cout << clr[i] << '\n';
    }
}

int main() {
    read();
    solve();
    print();
    return 0;
}