Cod sursa(job #2009983)

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

#define MAXN 100000

#define Inversions(x) ((x) * ((x) - 1) / 2)
#define Lsb(x) ((x) & -(x))

typedef long long int64;

int64 bit[MAXN + 1];

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;
}