Cod sursă (job #718167)

#include<fstream>
#include<cmath>
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;
int findk()
{
    int mnm = 2*n + 1, care = 1;
    for(int i=2;i<=n;i++)
    {
        if(2*((n-1)/i + 1) + i < mnm)
        {
            mnm = 2*((n-1)/i + 1) + i;
            care = i;
        }
    }
    return care;
}
signed main()
{
    fin>>n;
    k = findk();
    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

n/k + k + n/k




*/