Cod sursa(job #2773116)

Utilizator GligarEsterabadeyan Hadi Gligar Data 4 septembrie 2021 20:23:59
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>

using namespace std;

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

const int nmax=30000, n2max=(1<<15);

int v[n2max*2], sol[nmax+1];

int query(int nod, int l, int r, int p){
    v[nod]--;
    if(l==r){
        return nod;
    }else{
        if(v[nod*2]>=p){
            return query(nod*2,l,(r+l)/2,p);
        }else{
            return query(nod*2+1,(r+l)/2+1,r,p-v[nod*2]);
        }
    }
}

int main(){
    int n;
    fin>>n;
    int n2=1;
    while(n2<n){
        n2*=2;
    }
    for(int i=1;i<=n;i++){
        v[n2+i-1]=1;
    }
    for(int i=n2-1;i>=1;i--){
        v[i]=v[i*2]+v[i*2+1];
    }
    int p=2;
    for(int i=1;i<=n;i++){
        p=p+i-1;
        p=p%(n-i+1);
        if(p==0){
            p=1;
        }
        int x=query(1,1,n2,p);
        sol[i]=x-n2+1;
    }
    for(int i=1;i<=n;i++){
        fout<<sol[i]<<" ";
    }
    return 0;
}