Cod sursă (job #143346)

#include <cstdio>
#include <algorithm>
#define N 100010
using namespace std;
int n,i,A[N],B[N],*a,*b,*aux,poz[N],cod[N],m,p,j,k;
int main()
{
    freopen("specsort.in","r",stdin);
    freopen("specsort.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++){scanf("%d",&A[i]);poz[A[i]]=i;}
    a=A;b=B;
    for(i=1;i<=n;i++)
        if(!cod[i])
        {
            cod[i]=++k;
            for(j=i;poz[j]<poz[j+1]&&j<=n;j++)cod[j]=k;
        }
    for(;k>1;)
    {
        m=0;
        for(i=1;i<=n;i++)if(cod[a[i]]&1)b[++m]=a[i];
        for(i=1;i<=n;i++)if(!(cod[a[i]]&1))b[++m]=a[i];
        for(i=1;i<=n;i++)cod[i]=(cod[i]+1)/2;
        for(i=1;i<=n;i++)printf("%d ",b[i]);printf("\n");
        aux=a;a=b;b=aux;k=(k+1)/2;

    }
    return 0;
}