Cod sursa(job #3319937)

Utilizator Radu_VasileRadu Vasile Radu_Vasile Data 3 noiembrie 2025 20:55:49
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <sys/time.h>
#include <set>
#include <assert.h>
FILE *fin, *fout;
struct Treap{
  int key, priority;
  int sz;
  Treap *left;
  Treap *right;
};
int get_sz(Treap *t) {
  if(t == nullptr)
    return 0;
  return t->sz;
}
void rebuild(Treap *t) {
  if(t == nullptr)
    return;
  t->sz = 1 + get_sz(t->left) + get_sz(t->right);
}
std::pair<Treap*, Treap*> split(Treap *t, int key) {
  if(t == nullptr) {
    return {nullptr, nullptr};
  }else if(t->key <= key) {
    auto [first, second] = split(t->right, key);
    t->right = first;
    rebuild(t);
    rebuild(second);
    return {t, second};
  }else {
    auto [first, second] = split(t->left, key);
    t->left = second;
    rebuild(t);
    rebuild(first);
    return {first, t};
  }
}
Treap* merge(Treap *left, Treap* right) {
  if(left == nullptr) {
    return right;
  }
  else if(right == nullptr) {
    return left;
  }
  else if(left->priority > right->priority) {
    left->right = merge(left->right, right);
    rebuild(left);
    return left;
  } else {
    right->left = merge(left, right->left);
    rebuild(right);
    return right;
  }
}
Treap *insert(Treap *t, Treap *nd) {
  if(t == nullptr) {
    return nd;
  }
  if(nd->priority > t->priority) {
    auto [first, second] = split(t, nd->key);
    nd->left = first;
    nd->right = second;
    rebuild(nd);
    return nd;
  }
  if(t->key >= nd->key) {
    t->left = insert(t->left, nd);
    rebuild(t);
    return t;
  }else {
    t->right = insert(t->right, nd);
    rebuild(t);
    return t;
  }
}
Treap *insert(Treap *t, int key) {
  return insert(t, new Treap{
    .key = key,
    .priority = rand(),
    .sz = 1,
    .left = nullptr,
    .right = nullptr
  });
}
Treap *erase(Treap *t, int key) {
  if(t == nullptr){
    return nullptr;
  }
  if(t->key == key) {
    t = merge(t->left, t->right);
    rebuild(t);
    return t;
  }
  if(key <= t->key) {
    t->left = erase(t->left, key);
    rebuild(t);
    return t;
  }
  if(key > t->key) {
    t->right = erase(t->right, key);
    rebuild(t);
    return t;
  }
}
bool empty(Treap *t) {
  return (t == nullptr);
}

bool find_key(Treap *t, int key) {
  if(t == nullptr)
    return false;
  if(key == t->key)
    return true;
  return find_key(key <= t->key ? t->left : t->right, key);
}
int order_of_key(Treap *t, int key) {
  if(t == nullptr)
    return 0;
  if(t->key == key) {
    return get_sz(t->left);
  }if(t->key > key) {
    return order_of_key(t->left, key);
  }else if(t->key < key){
    return get_sz(t->left) + 1 + order_of_key(t->right, key);
  }
}
int find_by_order(Treap *t, int k) {
  if(t == nullptr)
    return -1;
  if(k < get_sz(t->left)) {
    return find_by_order(t->left, k);
  }else if(k == get_sz(t->left))
    return t->key;
  else {
    return find_by_order(t->right, k - get_sz(t->left) - 1);
  }
}
int main() {
  fin = fopen("order.in", "r");
  fout = fopen("order.out", "w");
  int n;
  fscanf(fin, "%d", &n);
  Treap *treap = nullptr;
  for( int i = 1; i <= n; i++ ) {
    treap = insert(treap, i);
  }
  int poz = 1;
  int i = 1;
  while(!empty(treap)) {
    poz %= get_sz(treap);
    int x = find_by_order(treap, poz);
    treap = erase(treap, x);

    fprintf(fout, "%d ", x);
    poz += i++;
  }
  fprintf(fout, "\n");
  fclose(fin);
  fclose(fout);
  return 0;
}