Cod sursă (job #143347)

//Cristian Lambru - Universitatea Bucuresti
//Solutie - O(sqrt(N)) - N egal cu numarul de subsiruri cu termeni consecutivi
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cmath>
using namespace std;

FILE *f = fopen("specsort.in", "r");
FILE *g = fopen("specsort.out", "w");

#define MaxN 50100

int N, nr, Sqrt;
int A[MaxN];
int viz[MaxN], vizSqrt[MaxN];
int aux[MaxN], vizSqrt2[MaxN];

void citire()
{
    fscanf(f,"%d",&N);
    for(int i=1;i<=N;i++)
        fscanf(f,"%d",&A[i]);
}

void precalculare(void)
{
    for(int i=1;i<=N;i++)
        if(!viz[A[i]-1])
            viz[A[i]] = A[i];
        else
            viz[A[i]] = viz[A[i]-1];

    for(int i=1;i<=N;i++)
        if(viz[i] != viz[i-1])
            vizSqrt[i] = ++nr;
        else
            vizSqrt[i] = vizSqrt[i-1];
}

void afisare(void)
{
    for(int i=1;i<=N;i++)
        fprintf(g,"%d ", A[i]);
    fprintf(g, "\n");
}

void extractSubseq(int a)
{
    int poz = N, poz1 = 0;

    for(int i=N;i;i--)
        if(vizSqrt[A[i]] != a)
            A[poz] = A[i],
            -- poz;
        else
            aux[++poz1] = A[i];

    for(int i=poz1;i;i--)
        A[poz1-i+1] = aux[i];
}

void extractSubseq2(int a)
{
    int poz = N, poz1 = 0;

    for(int i=N;i;--i)
        if(!vizSqrt2[A[i]] && A[i] == a)
            aux[++poz1] = A[i],
            vizSqrt2[A[i]] = 1,
            -- a;
        else
            A[poz] = A[i],
            -- poz;

    for(int i=poz1;i;i--)
        A[poz1-i+1] = aux[i];
}

void Rezolvare(void)
{
    for(int i=1;i<=N;i++)
        vizSqrt[i] = (vizSqrt[i]%Sqrt == 0) ? Sqrt : vizSqrt[i]%Sqrt;

    for(int i=Sqrt-1;i;i--)
    {
        extractSubseq(i);
        afisare();
    }

    int p = N;
    for(int i=N;i;i--)
        if(A[i] == p)
            vizSqrt2[p] = 1,
            --p;

    for(int i=N;i;i--)
        if(!vizSqrt2[i])
        {
            extractSubseq2(i);
            afisare();
        }
}

int main()
{
    citire();
    precalculare();

    Sqrt = sqrt(nr);      
        Rezolvare();
}