Cod sursa(job #2684242)

Utilizator eugen5092eugen barbulescu eugen5092 Data 13 decembrie 2020 13:13:38
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;
}