Cod sursa(job #3300496)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 16 iunie 2025 16:24:55
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <set>
#include <vector>
#include <bitset>

using namespace std;

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

typedef pair <int, int> pii;
const int nmax = 1e6;
int n, a[nmax + 2], b[nmax + 2];
int color[nmax + 2];
int value[nmax + 2];

int father[nmax + 2];
int getparent(int node){
    if(father[node] == node)
        return node;
    return father[node] = getparent(father[node]);
}

void showint(int x){
    if(x <= 9){
        out.put(x % 10 + '0');
    }else{
        showint(x / 10);
        out.put(x % 10 + '0');
    }
}

int main(){
    out.tie(NULL);
    in>>n>>a[1]>>b[1]>>value[1];

    for(int i = 1; i <= n; i++)
        father[i] = i;

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

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

        for(int it = a[i]; it <= b[i]; ){
            if(!color[it]){
                color[it] = value[i];
                father[it] = getparent(b[i] + 1);
            }

            it = getparent(it + 1);
        }
    }


    for(int i = 1; i <= n; i++){
        showint(color[i]);
        out.put('\n');
    }

    return 0;
}