Pagini recente » Cod sursa (job #2691530) | Cod sursa (job #614563) | Cod sursa (job #586696) | Cod sursa (job #3188384) | Cod sursa (job #2447393)
#include <bits/stdc++.h>
#define maxN 100002
using namespace std;
FILE *fin = freopen("order.in", "r", stdin);
FILE *fout = freopen("order.out", "w", stdout);
// Class to implement node
class Node
{
public:
int key;
Node **forward;
int *fDist;
Node(int, int);
};
Node::Node(int key, int level)
{
this->key = key;
// Allocate memory to forward
forward = new Node*[level+1];
fDist = new int[level + 1];
// Fill forward array with 0(NULL)
for (int i = 0; i <= level; ++ i) fDist[i] = 0;
memset(forward, 0, sizeof(Node*)*(level+1));
};
// Class for Skip list
class SkipList
{
// Maximum level for this skip list
int MAXLVL;
// P is the fraction of the nodes with level
// i pointers also having level i+1 pointers
float P;
// current level of skip list
int level, sz;
// pointer to header node
Node *header;
public:
SkipList(int, float);
int randomLevel();
Node* createNode(int, int);
void insertElement(int);
void deleteElement(int);
void searchElement(int);
int findKthElement(int);
};
SkipList::SkipList(int MAXLVL, float P)
{
this->MAXLVL = MAXLVL;
this->P = P;
level = 0;
// create header node and initialize key to -1
header = new Node(-1, MAXLVL);
};
// create random level for node
int SkipList::randomLevel()
{
float r = (float)rand()/RAND_MAX;
int lvl = 0;
while (r < P && lvl < MAXLVL)
{
lvl++;
r = (float)rand()/RAND_MAX;
}
return lvl;
};
// create new node
Node* SkipList::createNode(int key, int level)
{
Node *n = new Node(key, level);
return n;
};
// Insert given key in skip list
void SkipList::insertElement(int key)
{
Node *current = header;
// create update array and initialize it
Node *update[MAXLVL+1];
memset(update, 0, sizeof(Node*)*(MAXLVL+1));
/* start from highest level of skip list
move the current pointer forward while key
is greater than key of node next to current
Otherwise inserted current in update and
move one level down and continue search
*/
int pos[MAXLVL + 1];
memset(pos, 0, sizeof(pos));
for (int i = level; i >= 0; i--)
{
if (i != level) pos[i] = pos[i + 1];
while (current->forward[i] != NULL &&
current->forward[i]->key < key)
{
pos[i] += current->fDist[i];
current = current->forward[i];
}
update[i] = current;
}
/* reached level 0 and forward pointer to
right, which is desired position to
insert key.
*/
current = current->forward[0];
int K = pos[0] + 1;
/* if current is NULL that means we have reached
to end of the level or current's key is not equal
to key to insert that means we have to insert
node between update[0] and current node */
if (current != NULL && current->key == key)
{
for (int i = 0; i <= level; ++ i)
update[i]->fDist[i] ++;
return ;
}
if (current == NULL || current->key != key)
{
// Generate a random level for node
int rlevel = randomLevel();
++ sz;
// If random level is greater than list's current
// level (node with highest level inserted in
// list so far), initialize update value with pointer
// to header for further use
if (rlevel > level)
{
for (int i=level+1; i<rlevel+1; i++)
{
update[i] = header;
header->fDist[i] = sz;
}
// Update the list current level
level = rlevel;
}
// create new node with random level generated
Node* n = createNode(key, rlevel);
// insert node by rearranging pointers
for (int i=rlevel + 1; i<=level; i++)
update[i]->fDist[i] ++;
for (int i=0; i<=rlevel; i++)
{
n->fDist[i] = update[i]->fDist[i] + pos[i] - K + 1;
update[i]->fDist[i] = K - pos[i];
n->forward[i] = update[i]->forward[i];
update[i]->forward[i] = n;
}
//cout << "Successfully Inserted key " << key << "\n";
}
};
// Delete element from skip list
void SkipList::deleteElement(int key)
{
Node *current = header;
// create update array and initialize it
Node *update[MAXLVL+1];
memset(update, 0, sizeof(Node*)*(MAXLVL+1));
/* start from highest level of skip list
move the current pointer forward while key
is greater than key of node next to current
Otherwise inserted current in update and
move one level down and continue search
*/
int pos[MAXLVL + 1];
memset(pos, 0, sizeof(pos));
for (int i = level; i >= 0; i--)
{
if (i != level) pos[i] = pos[i + 1];
while (current->forward[i] != NULL &&
current->forward[i]->key < key)
{
pos[i] += current->fDist[i];
current = current->forward[i];
}
update[i] = current;
}
/* reached level 0 and forward pointer to
right, which is possibly our desired node.*/
current = current->forward[0];
// If current node is target node
if(current != NULL and current->key == key)
{
/* start from lowest level and rearrange
pointers just like we do in singly linked list
to remove target node */
-- sz;
for (int i = 0; i <= level; ++ i)
update[i]->fDist[i] --;
for(int i=0; i<=level; i++)
{
/* If at level i, next node is not target
node, break the loop, no need to move
further level */
if(update[i]->forward[i] != current)
break;
update[i]->fDist[i] += current->fDist[i];
current->fDist[i] = 0;
update[i]->forward[i] = current->forward[i];
}
// Remove levels having no elements
while(level>0 &&
header->forward[level] == 0)
level--;
//cout<<"Successfully deleted key "<<key<<"\n";
}
};
// Search for element in skip list
void SkipList::searchElement(int key)
{
Node *current = header;
/* start from highest level of skip list
move the current pointer forward while key
is greater than key of node next to current
Otherwise inserted current in update and
move one level down and continue search
*/
for(int i = level; i >= 0; i--)
{
while(current->forward[i] &&
current->forward[i]->key < key)
current = current->forward[i];
}
/* reached level 0 and advance pointer to
right, which is possibly our desired node*/
current = current->forward[0];
// If current node have key equal to
// search key, we have found our target node
//cout<<"Found key: "<<key<<"\n";
};
int SkipList::findKthElement(int k)
{
Node *current = header;
int pos = 0;
for(int i = level; i >= 0; i--)
{
while(current->forward[i] &&
pos + current->fDist[i] < k)
{
pos += current->fDist[i];
current = current->forward[i];
}
}
if (current->forward[0] == NULL) return -1;
return current->forward[0]->key;
};
SkipList lst(16, 0.5);
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
lst.insertElement(i);
int k = 1, N = n;
for (int i = 0; i < n; ++ i)
{
k = (k + i) % N;
int x = lst.findKthElement(k + 1);
printf("%d ", x);
lst.deleteElement(x);
-- N;
}
return 0;
}