Cod sursa(job #2010832)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 14 august 2017 14:59:13
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
#define Nmax 30001
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int arb[4*Nmax];
int poz,lsh,rsh,ex,val,ans;
void update(int nod, int p, int q)
{
    if(p==q)
        arb[nod]=1;
    else
    {
        int m=(p+q)/2;
        if(poz<=m)
            update(2*nod,p,m);
        else update(2*nod+1,m+1,q);
        arb[nod]=arb[2*nod]+arb[2*nod+1];
    }
}
void querry1(int nod, int p, int q)
{
    if(lsh<=p and q<=rsh)
        ex+=arb[nod];
    else
    {
        if(p==q) return;
        int m=(p+q)/2;
        if(m>=lsh) querry1(2*nod,p,m);
        if(m<rsh) querry1(2*nod+1,m+1,q);
    }
}
void querry2(int nod, int p, int q)
{
    if(p==q)
    {
        ans=p;
        arb[nod]=0;
    }
    else
    {
        int m=(p+q)/2;
        if(arb[2*nod]>=val) querry2(2*nod,p,m);
        else
        {
            val-=arb[2*nod];
            querry2(2*nod+1,m+1,q);
        }
        arb[nod]=arb[2*nod]+arb[2*nod+1];
    }
}
int main()
{
    int n;
    f>>n;
    for(int i=1;i<=n;i++)
    {
        poz=i;
        update(1,1,n);
    }
    int m=n+1;
    ans=1;
    for(int i=1;i<=n;i++)
    {
        --m;
        ex=0;
        lsh=1;
        rsh=ans;
        querry1(1,1,n);
        val=ex+i;
        while(val>m) val-=m;
        querry2(1,1,n);
        g<<ans<<' ';
    }

    return 0;
}