Pagini recente » Cod sursa (job #1052226) | Cod sursa (job #1020277) | Cod sursa (job #605291) | Cod sursa (job #3221158) | Cod sursa (job #1456895)
#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;
}