Cod sursa(job #2009975)

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

#define MAXN 100000

typedef long long int64;

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

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

int GetOrder(int inv, int n)
{
  int pos = 0;
  int 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(int pos, int n)
{
  while (pos <= n) {
    ++bit[pos];
    pos += Lsb(pos);
  }
}

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

int GetByOrder(int order, int n)
{
  int pos = 0;
  int 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");

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

  int 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 {
      int 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, "%d ", perm[i]);
  }
  return 0;
}