Pagini recente » Istoria paginii runda/ret1/clasament | Cod sursa (job #1428949) | Cod sursa (job #2073383) | Cod sursa (job #2070191) | Cod sursa (job #1456892)
#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;
}