Cod sursa(job #2592776)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 2 aprilie 2020 12:50:01
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>

using namespace std;

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

int ans,aint[130005],v[30005],n,n1,nr,actual;

void query(int nod,int l,int r,int sum){
    if(l==r){
        ans=l;
        return;
    }
    int mij=(l+r)>>1;
    if(sum<=aint[nod*2]){
        query(nod*2,l,mij,sum);
    }
    else{
        query(nod*2+1,mij+1,r,sum-aint[nod*2]);
    }
}

void update(int nod,int l,int r,int poz,int val){
    if(l==poz && r==poz){
        aint[nod]=val;
        return;
    }
    int mij;
    mij=(l+r)>>1;
    if(poz<=mij){
        update(nod*2,l,mij,poz,val);
    }
    else{
        update(nod*2+1,mij+1,r,poz,val);
    }
    aint[nod]=aint[nod*2]+aint[nod*2+1];

}


int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        update(1,1,n,i,1);
    }
    actual=1;
    n1=n;
    for(int i=1;i<=n;i++){
        actual+=i;
        actual%=n1;
        if(actual==0){
            actual=n1;
        }
        query(1,1,n,actual);
        cout<<ans<<" ";
        update(1,1,n,ans,0);
        n1--;
        actual--;
    }
    return 0;
}