Cod sursa(job #2009977)

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

#define MAXN 100000

typedef long long int64;

int64 inversions[MAXN + 1];
int64 bit[MAXN + 1];
int64 perm[MAXN];

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;
  inversions[2] = 1;
  for (i = 3; i <= n; ++i) {
    inversions[i] = inversions[i - 1] + i - 1;
  }

  for (i = 0; i < n; ++i) {
    int64 capacity = inversions[n - i - 1];
    if (capacity >= inv) {
      perm[i] = GetByOrder(1, n);
    } else {
      int64 order = GetOrder(inv, n - i);
      perm[i] = GetByOrder(order, n);
      inv -= (order - 1);
    }
    Update(perm[i], n);
  }

  for (i = 0; i < n; ++i) {
    fprintf(fout, "%lld ", perm[i]);
  }
  return 0;
}