Cod sursa(job #2447394)

Utilizator akaprosAna Kapros akapros Data 13 august 2019 11:36:59
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <assert.h>
#include <stdio.h>
#include <algorithm>


using std::pair;


struct Nod
{
  Nod* st;
  Nod* dr;
  int val;
  long long key;
  int size;
};


Nod* emptyNode;


bool isEmptyNode(Nod* rad) {
  return rad == emptyNode;
}


void recompute(Nod* nod) {
  nod->size = nod->st->size + 1 + nod->dr->size;
}


pair<Nod*, Nod*> split(Nod* rad, int sizeFirst) {
  assert(0 <= sizeFirst && sizeFirst <= rad->size);
  pair<Nod*, Nod*> answer;
  if (isEmptyNode(rad))
    answer.first = answer.second = emptyNode;
  else if (rad->st->size < sizeFirst)
  {
    pair<Nod*, Nod*> p = split(rad->dr, sizeFirst - rad->st->size - 1);
    answer.first = rad;
    rad->dr = p.first;
    answer.second = p.second;
    recompute(rad);
  }
  else // if (sizeFirst <= rad->st->size)
  {
    pair<Nod*, Nod*> p = split(rad->st, sizeFirst);
    answer.second = rad;
    rad->st = p.second;
    answer.first = p.first;
    recompute(rad);
  }


  return answer;
}


Nod* join(Nod* first, Nod* second) {
  if (isEmptyNode(first))
    return second;
  if (isEmptyNode(second))
    return first;
  if (second->key > first->key)
  {
    second->st = join(first, second->st);
    recompute(second);
    return second;
  } else // second->key <= first->key
  {
    first->dr = join(first->dr, second);
    recompute(first);
    return first;
  }
}


Nod* insert(Nod* rad, int index, int val) {
  assert(0 <= index && index <= rad->size);
  Nod* nodNou = new Nod();
  nodNou->val = val;
  nodNou->st = nodNou->dr = emptyNode;
  nodNou->key =((long long)rand() << 45
              ^ (long long)rand() << 30
              ^ (long long)rand() << 15
              ^ (long long)rand() <<  0)
              & 0x7fffffffffffffff;
  nodNou->size = 1;
  pair<Nod*, Nod*> p = split(rad, index);
  return join(join(p.first, nodNou), p.second);
}


int getKthElement(Nod* &rad, int index) {
  assert(0 <= index && index < rad->size);
  int ret;
  if (rad->st->size < index) {
    ret = getKthElement(rad->dr, index - rad->st->size - 1);
    recompute(rad);
  } else if (rad->st->size == index) {
    ret = rad->val;
    rad = join(rad->st, rad->dr);
  } else { // if (index < rad->st->size)
    ret = getKthElement(rad->st, index);
    recompute(rad);
  }
  return ret;
}


int main() {
  freopen("order.in", "r", stdin);
  freopen("order.out", "w", stdout);
  emptyNode = new Nod();
  emptyNode->val = 0;
  emptyNode->key = -1;
  emptyNode->st = emptyNode;
  emptyNode->dr = emptyNode;
  emptyNode->size = 0;

  int n;
  scanf("%d", &n);

  Nod* rad = emptyNode;
  for (int i = 1; i <= n; ++ i)
    rad = insert(rad, i - 1, i);

  int p = 1;
  for (int i = 1; i <= n; ++ i)
  {
    p = (p + i - 1) % (n - i + 1);
    printf("%d ", getKthElement(rad, p));
  }
  printf("\n");
  return 0;
}