Cod sursa(job #2009981)

Utilizator preda.andreiPreda Andrei preda.andrei Data 11 august 2017 13:38:59
Problema Farfurii Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>

#define MAXN 100000

typedef long long int64;

int64 bit[MAXN + 1];

int64 Inversions(int64 x) { return x * (x - 1) / 2; }

int64 Lsb(int64 x) { return x & (-x); }

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

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

void Update(int64 pos, int64 n)
{
  while (pos <= n) {
    ++bit[pos];
    pos += Lsb(pos);
  }
}

int64 GetCount(int64 pos)
{
  int64 count = 0;
  while (pos > 0) {
    count += bit[pos];
    pos -= Lsb(pos);
  }
  return count;
}

int64 GetByOrder(int64 order, int64 n)
{
  int64 pos = 0;
  int64 power = (1 << 18);

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

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, n);
    } else {
      int64 order = GetOrder(inv, n - i);
      number = GetByOrder(order, n);
      inv -= (order - 1);
    }

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