Cod sursa(job #1456895)

Utilizator retrogradLucian Bicsi retrograd Data 2 iulie 2015 13:05:52
Problema Sortare prin comparare Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.57 kb
#include <bits/stdc++.h>

using namespace std;
typedef int var;

#define DEBUG

#define del(V) { V.clear(); V.shrink_to_fit(); }

struct SkipList {

    #define MAXD 10
    #define INF (1 << 31 - 1)

    struct nod {
        var val, start;
        vector <nod*> next, prev;

        nod(var x) {
            val = x;
        }

        void detach() {
            for(var i=0; i<next.size(); i++) {
                nod *ant = prev[i], *nxt = next[i];

                ant->next[i] = nxt;
                nxt->prev[i] = ant;
            }

            del(next); del(prev);
        }

        void attach(nod *T[MAXD]) {

            //next.clear();
            //prev.clear();

            for(var i=0; i<MAXD; i++) {
                nod *ant = T[i], *nxt = ant->next[i];

                next.push_back(nxt);
                prev.push_back(ant);

                ant->next[i] = nxt->prev[i] = this;

                if(rand() % 3) break;
            }
        }
    };
    typedef nod* Node;


    Node head = new nod(-INF);
    Node tail = new nod(INF);
    Node stop[MAXD];

    SkipList() {
        for(var i=0; i<MAXD; i++) {
            head->next.push_back(tail);
            tail->prev.push_back(head);
        }
    }

    void insert(var val) {
        lowbound(val);
        Node node = new nod(val);
        node->attach(stop);
    }

    bool erase(var val) {
        Node p = find(val);
        if(p == NULL) return false;

        p->detach();
        delete p;
        return true;
    }

    Node lowbound(var val) {
        Node p = head;
        for(var i=MAXD-1; i>=0; i--) {
            while(p->next[i]->val <= val)
                p = p->next[i];
            stop[i] = p;
        }
        return p;
    }

    Node find(var val) {
        Node p = lowbound(val);
        if(p->val == val) return p;
        return NULL;
    }


    void dump(var d = 0) {
        cerr << "Dumping nodes at depth "<<d<<": \n";
        for(Node p = head->next[d]; p != tail; p = p->next[d])
            cerr << p->val << " ";
        cerr << endl;
    }

    void afis(ofstream &fout) {
        for(Node p = head->next[0]; p != tail; p = p->next[0])
            fout << p->val + 3 << " ";
        fout << endl;
    }

};
SkipList skip;


int main() {

    srand(time(NULL));

    ifstream fin("algsort.in");
    ofstream fout("algsort.out");

    var n, val;
    fin>>n;
    for(var i=1; i<=n; i++) {
        fin>>val;
        skip.insert(val - 3);
    }

    skip.afis(fout);


    return 0;
}