Cod sursă (job #143345)

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

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

#define MaxN 50100

int N, A[MaxN];
int viz[MaxN];

void citire(void)
{
    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];
}

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

    for(int i=N;i;i--)
    {
        if(A[i] == aux)
            -- aux, ++ nrElem;
        else
            A[poz] = A[i],
            -- poz;
    }

    for(int i=1;i<=nrElem;i++)
        A[i] = a-nrElem+i;
}

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

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

    for(int i=N;i;i--)
        if(viz[i] != viz[i+1])
        {
            extractSubseq(i);
            afisare();
        }
}