Cod sursa(job #2543354)

Utilizator DavidLDavid Lauran DavidL Data 11 februarie 2020 08:32:20
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("order.in");
ofstream fo("order.out");

struct Treap {
   Treap *left, *right;
   int val, priority;
   int subarb;

   Treap(int v, int p, int subarb, Treap *l, Treap *r) {
      this->val = v;
      this->priority = p;
      this->left = l; this->right = l;
      this->subarb = subarb;
   }
} *T, *nil;

int n;

int getRandom() {
   return 1LL * rand() % 10000 * 10000 + rand() % 10000;
}

void updSubarbore(Treap *nod) {
    if (nod == nil)
      return;
    nod->subarb = 1 + nod->left->subarb + nod->right->subarb;
}

void rotToRight(Treap *&nod) {
    Treap *t = nod->left;
    nod->left = t->right, t->right = nod;
    nod = t;

    updSubarbore(nod->right);
    updSubarbore(nod->left);
    updSubarbore(nod);
}

void rotToLeft(Treap *&nod) {
    Treap *t = nod->right;
    nod->right = t->left; t->left = nod;
    nod = t;

    updSubarbore(nod->right);
    updSubarbore(nod->left);
    updSubarbore(nod);
}


void balans(Treap *&nod) {
   // un fiu posibil sa nu fie bine ca heap
   if (nod->left->priority > nod->priority) {
      rotToRight(nod);
   }
   else if (nod->right->priority > nod->priority) {
      rotToLeft(nod);
   }
}

void baga(Treap *&nod, int val) {
   if (nod == nil) {
      // aici
      nod = new Treap(val, getRandom(), 1, nil, nil);
      return;
   }

   if (val <= nod->val) {
      // stanga
      baga(nod->left, val);
      updSubarbore(nod);
   }
   else {
      // dreapta
      baga(nod->right, val);
      updSubarbore(nod);
   }

   balans(nod);
}

bool cauta(Treap *nod, int x) {
    if (nod == nil)
        return 0;

    if (nod->val == x)
        return 1;
    if (x <= nod->val)
        return cauta(nod->left, x);
    else
        return cauta(nod->right, x);
}

void scoate(Treap *&nod, int val) {
    if (nod == nil)
        return;

    if (val < nod->val) {
        scoate(nod->left, val);
        updSubarbore(nod);
    }
    else if (val > nod->val) {
        scoate(nod->right, val);
        updSubarbore(nod);
    }
    else {
        // sunt aici si vreau sa cobor. il aduc pe fiul cu prioritate mai mare
        if (nod->left == nil && nod->right == nil) {
            delete nod;
            nod = nil;
        }
        else {
            if (nod->left->priority > nod->right->priority)
                rotToRight(nod);
            else
                rotToLeft(nod);
            scoate(nod, val);
        }
    }
}

int kthElement(Treap *nod, int k) {
    if (nod == nil)
        return -1;

    // st: 1...nod->left->subarb
    if (k <= nod->left->subarb)
        return kthElement(nod->left, k);
    else if (k == nod->left->subarb + 1)
        return nod->val;
    else
        return kthElement(nod->right, k - (nod->left->subarb + 1));
}

int main()
{
   srand(time(NULL));

   T = nil = new Treap(0, 0, 0, NULL, NULL);

   fi >> n;

   for (int i = 1; i <= n; i++) {
      baga(T, i);
   }

   int curr = 2, total = n;
   for (int i = 2; i <= n; i++) {
      int x = kthElement(T, curr);
      fo << x << " ";

      scoate(T, x);

      total--;
      curr = (curr + i - 1) % total;
      if (curr == 0)
         curr = total;
   }
   fo << kthElement(T, curr);


   return 0;
}