Cod sursă (job #811841)

#include <fstream>
#include <cmath>
using namespace std;
ifstream cin("arbperm2.in");
ofstream cout("arbperm2.out");
const int N=1e5+5;
int n,k,p[N],aib[N];
void update(int poz,int val)
{
    for(int i=poz; i<=n; i+=(i&-i))
        aib[i]+=val;
}
int query(int poz)
{
    int sum=0;
    for(int i=poz; i>0; i-=(i&-i))
        sum+=aib[i];
    return sum;
}
int get_kth(int val)
{
    int pos=0;
    int p2=log2(n);
    int interval=(1<<p2);
    for(int i=interval; i>0; i/=2)
    {
        if(pos+i<=n&&i-aib[pos+i]<=val)
        {
            val-=(i-aib[pos+i]);
            pos+=i;

        }
    }
    return pos;
}
int ord[N];
void semi()
{
    for(int i=1; i<=n; i++)
    {
        ord[p[i]]=query(p[i]);
        update(p[i],1);
    }
}
void advance()
{
    for(int i=n;i>=1;i--)
    {
        int old=k;
        k=(ord[i]+k)/i;
        ord[i]=(ord[i]+old)%i;
    }
}
int ans[N];
void put()
{
    for(int i=1;i<=n;i++)
    aib[i]=0;

    for(int i=n;i>=1;i--)
    {
        int pos=get_kth(ord[i]);
        ans[pos+1]=i;
        update(pos+1,1);

    }
}
void read()
{
    cin>>n>>k;
    for(int i=1; i<=n; i++)
        cin>>p[i];

}
int main()
{
    read();
    semi();
    advance();
    put();
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";

    return 0;
}