Cod sursa(job #3170009)

Utilizator Allie28Radu Alesia Allie28 Data 16 noiembrie 2023 17:03:25
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

const int LMAX = 1000005;
int a[LMAX], b[LMAX], c[LMAX], exactcol[LMAX], nxt[LMAX];
bool col[LMAX];

int findnext(int x) {
    if (nxt[x] == x+1) {
        return x;
    }
    int root = findnext(nxt[x]);
    nxt[x] = root;
    return root;
}

void unite(int x, int mainparent) {
    int rx = findnext(x);
    if (mainparent > rx) {
        nxt[rx] = mainparent;
    }
    else {
        nxt[mainparent] = rx; ///daca gasim o secv de culori care depasteste y ul
    }
}


int main() {
    int n;
    fin >> n >> a[1] >> b[1] >> c[1];
    nxt[1] = 2;
    for (int i = 2; i < n ; i++) {
        a[i] = (a[i-1] * i) % n;
        b[i] = (b[i-1] * i) % n;
        c[i] = (c[i-1] * i) % n;
        nxt[i] = i+1;
    }

    for (int i = n-1; i > 0; i--) {
        int x, y, mainparent;
        x = min(a[i], b[i]);
        y = max(a[i], b[i]);
        mainparent = y;
        while (x <= y) {
            int nx = findnext(x) + 1;
            if (!col[x]) {
                col[x] = true;
                exactcol[x] = c[i];
            }
            unite(x, mainparent);
            x = nx;
        }
    }

    for (int i = 1; i < n; i++) {
        fout << exactcol[i]<<endl;
    }

    fin.close();
    fout.close();

    return 0;
}