Cod sursă (job #161192)

#include <cstdio>

#define MAX_N 50000

int v[1 + MAX_N], p2[20], po[1 + MAX_N];

struct sp
{
  int val;
  int norm;
} vl[1 + MAX_N], v2[1 + MAX_N];

int main() {
  freopen("specsort.in", "r", stdin);
  freopen("specsort.out", "w", stdout);
  int n, m, i, j, nr, x;
  scanf("%d", &n);
  p2[0] = 1;
  for (i = 1; i <= 19; i++)
    p2[i] = p2[i - 1] * 2;
  for (i = 1; i <= n; i++)
  {
    scanf("%d", &v[i]);
    po[v[i]] = i;
    vl[i].val = v[i];
  }
  nr = 0;
  vl[po[1]].norm = 0;
  for (i = 2; i <= n; i++)
  {
    if (po[i - 1] < po[i])
      vl[po[i]].norm = vl[po[i - 1]].norm;
    else {
      nr++;
      vl[po[i]].norm = nr;
    }
  }

  for (i = 0; i <= 19; i++)
    if (nr & p2[i])
      x = i;
  //printf("%d\n", nr);
  //printf("%d\n", x + 1);
  //for (i = 1; i <= n; i++)
  //  printf("%d ", vl[i].norm);
  //printf("\n");
  //for (i = 1; i <= n; i++)
  //  printf("%d ", v[i]);
  //printf("\n");
  for (i = 0; i <= x; i++)
  {
    m = 0;
    for (j = 1; j <= n; j++)
      if (!(vl[j].norm & p2[i]))
      {
        m++;
        v2[m] = vl[j];
      }
    for (j = 1; j <= n; j++)
    {
      if (vl[j].norm & p2[i])
      {
        m++;
        v2[m] = vl[j];
      }
      vl[j] = v2[j];
      printf("%d ", vl[j].val);
    }
    printf("\n");
  }

  return 0;
}