Cod sursa(job #2692578)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 3 ianuarie 2021 11:35:57
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream ci("order.in");
ofstream cou("order.out");
 
int n,N;
int aint[120005];
 
void Build(int nod,int st,int dr){
    if(st==dr){
        aint[nod]=1;
    }else{
        int m=(st+dr)/2;
        Build(nod*2,st,m);
        Build(nod*2+1,m+1,dr);
        aint[nod]=aint[nod*2]+aint[nod*2+1];
    }
}
 
void cit(){
    int i;
    ci>>n;
    N=1;
    Build(1,1,n);
}
 
void Update(int nod,int p,int st,int dr)
{
    if(st==dr){
        aint[nod]=0;
    }else{
        int m=(st+dr)/2;
        if(p<=m){
            Update(nod*2,p,st,m);
        }else{
            Update(nod*2+1,p,m+1,dr);
        }
        aint[nod]=aint[nod*2]+aint[nod*2+1];
    }
 
}
 
int Query(int nod, int x,int y,int k)
{
    int m;
    if(x==y) return x;
    else
    {
        m = (x + y) / 2;
        if(k <= aint[nod*2]) return Query(nod * 2,x,m,k);
        else {
            return Query(nod*2+1,m+1,y,k-aint[nod*2]);
        }
 
    }
}
 
 
void rez(){
    int k,poz=2;
    for(int i=1;i<=n;i++){
        poz=poz+i-1;
        while(poz>aint[1]){
            poz-=aint[1];
        }
        k=Query(1,1,n,poz);
        Update(1,k,1,n);
        cou<<k<<" ";
    }
 
}
 
int main()
{
    cit();
    rez();
    return 0;
}