Cod sursa(job #2538878)

Utilizator DavidLDavid Lauran DavidL Data 5 februarie 2020 11:56:53
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 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) {
      val = v;
      priority = p;
      left = 0; right = 0;
      subarb = 0;
   }
};

Treap *T = new Treap;

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

void rotToRight(Treap *nod) {
   Treap *oldNodLR = nod->left->right;

   nod->left->right = nod;
   nod = nod->left;
   nod->right->left = oldNodLR;
}

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

   nod->right->left = nod;
   nod = nod->right;
   nod->left->right = oldNodRL;
}

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

void baga(Treap *nod, int val) {
   if (nod == 0) {
      // aici
      nod = Treap(val, getRandom());
      return;
   }

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

   balans(nod);
}

int kthElement(Treap *nod, int k) {
   
}

int main()
{
   fi >> n;

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

   int curr = 1, total = n;
   for (int i = 1; i <= n; i++) {
      fo << kthElement(R, curr) << " ";

      total--;
      curr = (curr + i - 1) % total;
      if (curr == 0)
         curr = total;
   }


   return 0;
}