Cod sursă (job #161191)

#include <cstdio>

int v[50005], p2[25], po[50005];

struct sp
{
  int val;
  int norm;
} vl[50005], v2[50005];

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;
  nr = 0;
  for (i = 1; i <= 20; 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];
  }
vl[po[1]].norm=0;
nr=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;
    }
  }


  nr--;
  for (i = 0; i <= 20; i++)
    if (nr & p2[i])
      x = i;
//  printf("%d\n", x);
//  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;
}