Cod sursa(job #2014820)

Utilizator victoreVictor Popa victore Data 24 august 2017 14:55:40
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<cstdio>

using namespace std;

const int nmax=(1e5+5);

int arb[nmax<<2],ans=1,last,l,r;

inline void buildtree(int node,int st,int dr)
{
    if(st==dr)
    {
        arb[node]=1;
        return;
    }
    int med=((dr-st)>>1) +st;
    buildtree(node<<1,st,med);
    buildtree(node<<1|1,med+1,dr);
    arb[node]=arb[node<<1] + arb[node<<1|1];
}

inline void query1(int node,int st,int dr)
{
    if(l <= st && dr <= r)
    {
        last+=arb[node];
        return;
    }
    if(st == dr)
        return;
    int med=((dr-st)>>1)+st;
    query1(node<<1 ,st , med);
    query1(node<<1|1,med+1,dr);
}

inline void query(int node,int st,int dr,int val)
{
    if(st==dr)
    {
        ans=st;
        arb[node]=0;
        return;
    }
    int med=((dr-st)>>1)+st;
    if(arb[node<<1] && val - arb[node<<1] <= 0)
        query(node<<1 , st ,med , val);
    else
        query(node<<1|1 , med+1 ,dr , val-arb[node<<1]);
    arb[node]=arb[node<<1] + arb[node<<1|1];
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int n,i,j,poz=1,lng;
    scanf("%d",&n);
    buildtree(1 , 1 ,n);
    lng=n+1;
    for(i=1;arb[1];i++,lng--)
    {
        l=1,r=ans;
        last=0;
        query1(1 , 1 , n);
        poz=last+i;
        while(poz > lng)
            poz-=lng;
        query(1 , 1 , n , poz);
        printf("%d ",ans);
    }
}