Cod sursă (job #730409)

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
const int NIL = -1;

ifstream fin( "arbperm.in" );
ofstream fout( "arbperm.out" );

int v[NMAX+1];
int poz[NMAX+1];
int aib[NMAX+1];
int n;

void update( int poz ) {
  while( poz <= n ) {
    aib[poz]++;
    poz += ( poz & ( -poz ) );
  }
}

int query( int poz ) {
  int sum = 0;
  while( poz ) {
    sum += aib[poz];
    poz -= ( poz & ( -poz ) );
  }
  return sum;
}

int ans[NMAX+1];
int perm[NMAX+1];

int main() {
  int i, k, rest, p, cop, st, dr, mij;
  fin >> n >> k;
  for( i = 0; i < n; i++ )
    fin >> v[i];
  for( i = 0; i < n; i++ ) {
    poz[v[i]] = query( v[i] );
    update( v[i] );
  }
  for( i = n; i >= 2; i-- ) {
    rest = k % i;
    poz[i] = poz[i] + rest;
    k = k / i;
    if( poz[i] >= i )
      poz[i] %= i, k++;
  }
  for( i = 0; i <= n; i++ )
    aib[i] = 0;
  for( i = n; i >= 1; i-- ) {
    p = poz[i] + 1;
    st = 1;
    dr = n + 1;
    while( dr - st > 1 ) {
      mij = ( st + dr ) / 2;
      if( query( mij ) + p > mij )
        st = mij;
      else
        dr = mij;
    }
    if( st - query( st ) == p )
      ans[i] = st;
    else
      ans[i] = dr;
    update( ans[i] );
  }
  for( i = 1; i <= n; i++ )
    perm[ans[i]] = i;
  for( i = 1; i <= n; i++ )
    fout << perm[i] << " ";
  return 0;
}