Cod sursă (job #143343)

//Cristian Lambru - Universitatea Bucuresti
//Liste alocate dinamic - 100pt
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdio>
using namespace std;

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

int N,nr;

typedef struct _nod
{
    int info, nr;
    _nod *next, *prev;
} nod;

void pushTop(nod* start, nod *nou)
{
    start->next->prev = nou;
    nou->next = start->next;
    nou->prev = start;
    start->next = nou;
}

void pushBack(nod* start, nod *nou)
{
    start->prev->next = nou;
    nou->next = start;
    nou->prev = start->prev;
    start->prev = nou;
}

void afisare(nod *start)
{
    for(nod *q = start->next;q != start;q = q->next)
        fprintf(g,"%d ",q->info);

    fprintf(g, "\n");
}

void concat(nod *startOut, nod *startIn)
{
    startIn->prev->next = startOut->next;
    startOut->next->prev = startIn->prev;
    startIn->next->prev = startOut;
    startOut->next = startIn->next;

    startIn->next = startIn->prev = startIn;
}

inline void remove(nod *q)
{
    q->next->prev = q->prev;
    q->prev->next = q->next;
}

nod *startA, *startAux;

void citire(void)
{
    int a;

    startA = new nod;
    startA->next = startA->prev = startA;

    fscanf(f,"%d ",&N);
    for(int i=1;i<=N;i++)
    {
        fscanf(f,"%d ",&a);
        nod *nou = new nod;
        nou->info = nou->nr = a;
        pushBack(startA, nou);
    }
}

void precalculare(void)
{
    vector<int> A;

    for(int i=0;i<=N;i++)
        A.push_back(0);

    for(nod *q = startA->next;q != startA;q = q->next)
        if(A[q->info-1])
            A[q->info] = A[q->info-1];
        else
            A[q->info] = q->info;

    A[1] = 0;
    for(int i=2;i<=N;i++)
        if(A[i] == i)
            A[i] = A[i-1] + 1;
        else
            A[i] = A[i-1];

    for(nod *q = startA->next;q != startA;q = q->next)
        q->nr = A[q->info];

    nr = A[N]; 
}

void Rezolvare(void)
{
    startAux = new nod;
    startAux->next = startAux->prev = startAux;

    for(int i=0;(1<<i)<=nr;i++)
    {
        for(nod *q = startA->next;q != startA;q = q->next)
            if((q->nr & (1<<i)) == 0)
            {
                nod *a = q->prev;
                remove(q);
                pushBack(startAux, q);
                q = a;
            }

        concat(startA, startAux);

        afisare(startA);
    }
}

int main()
{
    citire();

    precalculare();
    afisare(startA);
    Rezolvare();
}