Cod sursa(job #1456892)

Utilizator retrogradLucian Bicsi retrograd Data 2 iulie 2015 12:56:29
Problema Sortare prin comparare Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.53 kb
#include <bits/stdc++.h>

using namespace std;
typedef int var;

#define DEBUG

struct SkipList {

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

    struct nod {
        var val, start;
        nod *next[MAXD], *prev[MAXD];

        nod(var x) {
            val = x;
            start = MAXD;
        }

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

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

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

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

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

                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[i] = tail;
        head->start = 0;
    }

    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=0; i<MAXD; 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 = MAXD - 1) {
        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) {
        var d = MAXD - 1;
        for(Node p = head->next[d]; p != tail; p = p->next[d])
            fout << p->val + 3 << " ";
        fout << endl;
    }

};
SkipList skip;


int main() {

    vector<var> Values = {2, 7, 11, 5, 4, 2, 8, 10};

    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;
}