Cod sursa(job #2447393)

Utilizator akaprosAna Kapros akapros Data 13 august 2019 11:35:54
Problema Order Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 7.85 kb
#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;
}