Cod sursă (job #144707)

#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXN 100010
int A[MAXN], B[MAXN], Poz[MAXN], Q[MAXN];
bool Ok[MAXN];
int N, nr;

int main()
{
	freopen("specsort.in","r",stdin);
	freopen("specsort.out","w",stdout);

	scanf("%d", &N);
	for (int i = 1; i <= N; ++i){
		scanf("%d", &A[i]);
		Poz[A[i]] = i;
	}

	nr = -1;
	Q[++nr] = 1;
	for (int i = 2; i <= N; ++i)
		if (Poz[i] < Poz[i - 1])
			Q[++nr] = i;
	Q[nr + 1] = N + 1;

	for (int i = 0; (1 << i) <= nr; ++i){
		for (int j = 1; j <= N; ++j)
			Ok[j] = false;
		for (int j = 0; j <= nr; ++j){
			if (j & (1<<i)) continue;
			for (int t = Q[j]; t < Q[j+1]; ++t)
				Ok[t] = true;
		}
		int t = 0;
		for (int j = 1; j <= N; ++j)
			if (Ok[A[j]])
				B[++t] = A[j];
		for (int j = 1; j <= N; ++j)
			if (!Ok[A[j]])
				B[++t] = A[j];

		for (int j = 1; j <= N; ++j){
			A[j] = B[j];
			printf("%d ", A[j]);
		}
		printf("\n");
	}

	return 0;
}