Cod sursă (job #730414)

#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, j, k, rest, p, cop, st, dr, mij, p2, pos;
  fin >> n >> k;
  p2 = 1;
  while( p2 * 2 < n )
    p2 *= 2;
  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;
    pos = 0;
    for( j = p2; j >= 1; j /= 2 ) {
      if( j - aib[pos+j] < p ) {
        pos += j;
        p -= ( j - aib[pos] );
      }
    }
    ans[i] = pos + 1;
    update( ans[i] );
  }
  for( i = 1; i <= n; i++ )
    perm[ans[i]] = i;
  for( i = 1; i <= n; i++ )
    fout << perm[i] << " ";
  return 0;
}