Cod sursa(job #3170020)

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

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

const int LMAX = 1000000;
int a[LMAX], b[LMAX], c[LMAX], exactcol[LMAX], nxt[LMAX];

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


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;
        x = min(a[i], b[i]);
        y = max(a[i], b[i]);
        while (x < y) {
            if (!exactcol[x]) {
                exactcol[x] = c[i];
                x++;
                nxt[x] = y;
            }
            else {
                int rx = findnext(x);
                x = rx + 1;
                if (rx > y) {
                    nxt[y] = rx;
                }
                else {
                    nxt[rx] = y;
                }
            }
        }
        if (x == y) {
            if (!exactcol[x]) {
                exactcol[x] = c[i];
            }
            else {
                int rx = findnext(x);
                x = rx + 1;
                if (rx > y) {
                    nxt[y] = rx;
                }
                else {
                    nxt[rx] = y;
                }
            }
        }
    }

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

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

    return 0;
}