Cod sursa(job #2794318)

Utilizator GligarEsterabadeyan Hadi Gligar Data 4 noiembrie 2021 17:39:07
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>

using namespace std;

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

const int nmax=1000000;

typedef long long int64;

int A[nmax+1], B[nmax+1], C[nmax+1], r[nmax+1], sol[nmax+1];

void update(int x){
    int i=x;
    while(r[i]!=r[r[i]]){
        i=r[i];
    }
    int j=x;
    while(r[j]!=r[r[j]]){
        int rj=r[j];
        r[j]=r[i];
        j=rj;
    }
}

int maxi(int a, int b){
    if(a>b){
        return a;
    }else{
        return b;
    }
}

int main(){
    int n;
    fin>>n>>A[1]>>B[1]>>C[1];
    for(int i=2;i<=n-1;i++){
        A[i]=(int64(A[i-1])*i)%n;
        B[i]=(int64(B[i-1])*i)%n;
        C[i]=(int64(C[i-1])*i)%n;
    }
    for(int i=1;i<=n;i++){
        r[i]=i;
    }
    for(int i=n-1;i>=1;i--){
        int b=maxi(A[i],B[i]);
        int a=A[i]+B[i]-b;
        update(a);
        for(int j=r[a];j<=b;j=r[j+1]){
            sol[j]=C[i];
            update(j+1);
            r[j]=r[j+1];
        }
    }
    for(int i=1;i<=n-1;i++){
        fout<<sol[i]<<"\n";
    }
    return 0;
}