Cod sursa(job #3300469)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 16 iunie 2025 13:14:42
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <set>
#include <vector>
#include <bitset>

using namespace std;

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

const int nmax = 1e6;
int n, a[nmax + 2], b[nmax + 2];
int color[nmax + 2];
int value[nmax + 2];

vector <int> lf[nmax + 2];
vector <int> rg[nmax + 2];

bitset <nmax + 2> inuse;

int main(){

    in>>n>>a[1]>>b[1]>>value[1];

    for(int i = 2; i <= n - 1; i++){
        a[i] = (a[i - 1] * i) % n;
        b[i] = (b[i - 1] * i) % n;
        value[i] = (value[i - 1] * i) % n;
    }

    n--; ///op from a, b, value for [1, 2, ..., n - 1]
    for(int i = 1; i <= n; i++){
        if(a[i] > b[i]) swap(a[i], b[i]);

        lf[a[i]].push_back(i);
        rg[b[i]].push_back(i);
    }

    for(int i = 1; i <= n; i++){
        for(auto it : lf[i])
            inuse[it] = 1;

        for(int it = n; it >= 1; it--){
            if(inuse[it]){
                color[i] = value[it];
                break;
            }
        }

        for(auto it : rg[i])
            inuse[it] = 0;
    }

    for(int i = 1; i <= n; i++)
        out<<color[i]<<"\n";

    return 0;
}