Cod sursa(job #3240534)

Utilizator EricRaiaEricRaia EricRaia Data 16 august 2024 10:49:20
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>

using namespace std;

ifstream cin ("order.in");
ofstream cout ("order.out");

int n,A[30002<<2];
void build(int nod, int st, int dr){
    if(st==dr){
        A[nod]=1;
    }else{
        int mij=(st+dr)>>1;
        build((nod<<1),st,mij);
        build((nod<<1)+1,mij+1,dr);
        A[nod]=A[(nod<<1)]+A[(nod<<1)+1];
    }
}
void update(int nod, int st, int dr, int pos, int val){
    if(st==dr)
        A[nod]=val;
    else{
        int mij=(st+dr)>>1;
        if(pos<=mij)
            update((nod<<1),st,mij,pos,val);
        if(mij<pos)
            update((nod<<1)+1,mij+1,dr,pos,val);
        A[nod]=A[(nod<<1)]+A[(nod<<1)+1];
    }
}
int query(int nod, int st, int dr, int pos){
    if(st==dr)
        return st;
    else{
        int mij=(st+dr)>>1;
        if(A[(nod<<1)]>=pos)
            return query((nod<<1),st,mij,pos);
        return query((nod<<1)+1,mij+1,dr,pos-A[(nod<<1)]);
    }
}
int main(){
    cin>>n;
    build(1,1,n);
    for(int i=1,pos=1,kuery;i<=n;i++){
        pos=(pos+i)% A[1];
        if(pos==0)
            pos=A[1];
        kuery=query(1, 1, n, pos);
        update(1, 1, n, kuery, 0);
        pos -= 1;
        cout<<kuery<< ' ';
    }
    return 0;
}