Cod sursă (job #718164)

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
ifstream fin("specsort.in");
ofstream fout("specsort.out");
int n,k;
int p[50005];
int inc[50005],cnti;
int sf[50005],cnts;
signed main()
{
    fin>>n;
    k = sqrt(n);
    for(int i=1;i<=n;i++)
    {
        fin>>p[i];
    }
    int poz=n,nxt;
    while(poz>1)
    {
        cnti=0;
        cnts=0;
        if(poz==n && n%k!=0)
            nxt = n - n%k;
        else
            nxt = poz - k;
        for(int j=1;j<=n;j++)
        {
            if(p[j]>nxt && p[j]<=poz)
                inc[++cnti]=p[j];
            else
                sf[++cnts]=p[j];
        }
        for(int j=1;j<=cnti;j++)
        {
            fout<<inc[j]<<" ";
            p[j]=inc[j];
        }
        for(int j=1;j<=cnts;j++)
        {
            fout<<sf[j]<<" ";
            p[cnti+j]=sf[j];
        }
        fout<<"\n";
        poz=nxt;
    }
    for(int i=k;i>0;i--)
    {
        cnti=0;
        cnts=0;
        for(int j=1;j<=n;j++)
        {
            if(p[j]%k == i%k)
                inc[++cnti]=p[j];
            else
                sf[++cnts]=p[j];
        }
        for(int j=1;j<=cnti;j++)
        {
            fout<<inc[j]<<" ";
            p[j]=inc[j];
        }
        for(int j=1;j<=cnts;j++)
        {
            fout<<sf[j]<<" ";
            p[cnti+j]=sf[j];
        }
        fout<<"\n";
    }
    poz=n;
    while(poz>1)
    {
        cnti=0;
        cnts=0;
        if(poz==n && n%k!=0)
            nxt = n - n%k;
        else
            nxt = poz - k;
        for(int j=1;j<=n;j++)
        {
            if(p[j]>nxt && p[j]<=poz)
                inc[++cnti]=p[j];
            else
                sf[++cnts]=p[j];
        }
        for(int j=1;j<=cnti;j++)
        {
            fout<<inc[j]<<" ";
            p[j]=inc[j];
        }
        for(int j=1;j<=cnts;j++)
        {
            fout<<sf[j]<<" ";
            p[cnti+j]=sf[j];
        }
        fout<<"\n";
        poz=nxt;
    }
    return 0;
}
/**

9 8 7 6 5 4 3 2 1





*/