Cod sursa(job #2493552)

Utilizator Alexandru_StoianStoian Sorin Alexandru Alexandru_Stoian Data 16 noiembrie 2019 14:09:13
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("order.in");
ofstream g("order.out");

int arb[400001],n,val,nr,s;

void build(int nod, int st, int dr){
    if(st==dr){
        arb[nod]=1;
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    arb[nod]=arb[nod*2]+arb[nod*2+1];
}

void updt(int nod, int st, int dr, int val){
    if(st==dr){
        arb[nod]=0;
        return;
    }
    int mij=(st+dr)/2;
    if(val<=mij)updt(nod*2,st,mij,val);
    else updt(nod*2+1,mij+1,dr,val);
    arb[nod]=arb[nod*2]+arb[nod*2+1];
}

void qry(int nod, int st, int dr, int val){
    if(st==dr){
        s=st;
        return;
    }
    int mij=(st+dr)/2;
    if(arb[nod*2]>=val)qry(nod*2,st,mij,val);
    else qry(nod*2+1,mij+1,dr,val-arb[nod*2]);
}

int main(){
    f>>n;

    build(1,1,n);

    val=1;
    nr=n;

    for(int i=1; i<=n; ++i){
        val=val+i;
        val=val%nr;
        if(val==0)val=nr;
        s=0;
        qry(1,1,n,val);
        updt(1,1,n,s);
        --nr;
        --val;
        g<<s<<' ';
    }
    return 0;
}