Cod sursa(job #2010001)

Utilizator preda.andreiPreda Andrei preda.andrei Data 11 august 2017 14:24:36
Problema Farfurii Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>

#define MAXN 100000

#define Inversions(x) ((x) * ((x) - 1) / 2)
#define LeftSon(x) ((x) << 1)
#define RightSon(x) (((x) << 1) + 1)

typedef long long int64;

int64 seg[4 * MAXN + 4];

int64 GetOrder(int64 inv, int64 n)
{
  int64 pos = 0;
  int64 power = (1 << 17);

  while (power > 0) {
    if (pos + power < n && inv - (pos + power - 1) > Inversions(n - 1)) {
      pos += power;
    }
    power >>= 1;
  }
  return pos + 1;
}

void Update(int node, int left, int right, int pos)
{
  if (left == right) {
    seg[node] = 1;
    return;
  }

  int mid = left + (right - left) / 2;
  if (pos <= mid) {
    Update(LeftSon(node), left, mid, pos);
  } else {
    Update(RightSon(node), mid + 1, right, pos);
  }
  seg[node] = seg[LeftSon(node)] + seg[RightSon(node)];
}

int64 GetByOrder(int node, int left, int right, int order)
{
  if (left == right) {
    return left;
  }

  int mid = left + (right - left) / 2;
  int left_len = mid - left + 1;

  if (left_len - seg[LeftSon(node)] >= order) {
    return GetByOrder(LeftSon(node), left, mid, order);
  }
  order -= (left_len - seg[LeftSon(node)]);
  return GetByOrder(RightSon(node), mid + 1, right, order);
}

int main()
{
  FILE *fin = fopen("farfurii.in", "r");
  FILE *fout = fopen("farfurii.out", "w");

  int64 n, inv;
  fscanf(fin, "%lld%lld", &n, &inv);

  int64 i;
  for (i = 0; i < n; ++i) {
    int64 capacity = Inversions(n - i - 1);
    int64 number = 0;

    if (capacity >= inv) {
      number = GetByOrder(1, 1, n, 1);
    } else {
      int64 order = GetOrder(inv, n - i);
      number = GetByOrder(1, 1, n, order);
      inv -= (order - 1);
    }

    Update(1, 1, n, number);
    fprintf(fout, "%lld ", number);
  }
  return 0;
}