Cod sursa(job #3300481)

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

#include <utility>
#define x first
#define y second
#include <algorithm>

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];

pii lf[nmax + 2];
pii rg[nmax + 2];
int idxlf = 1, idxrg = 1;
bitset <nmax + 2> inuse;

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 = 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 = 1; i <= n; i++){
        if(a[i] > b[i]) swap(a[i], b[i]);

        lf[i] = make_pair(a[i], i);
        rg[i] = make_pair(b[i], i);
    }

    sort(lf + 1, lf + 1 + n);
    sort(rg + 1, rg + 1 + n);

    for(int i = 1; i <= n; i++){
        for(; idxlf <= n && lf[idxlf].x <= i; idxlf++)
            inuse[lf[idxlf].y] = 1;

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

        for(; idxrg <= n && rg[idxrg].x <= i; idxrg++)
            inuse[rg[idxrg].y] = 0;
    }

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

    return 0;
}