Cod sursa(job #2019974)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 9 septembrie 2017 01:27:15
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.74 kb
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long LL;

#ifdef INFOARENA
#define ProblemName "farfurii"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

const int MAXN = 100010;
int arbInt[MAXN << 2];
int N, arbSz;

inline int leftSon(int x) {
  return x * 2 + 1;
}

inline int rightSon(int x) {
  return x * 2 + 2;
}

inline int parent(int x) {
  return (x - 1) >> 1;
}

void pre() {
  arbSz = 1;
  while (arbSz < N)
    arbSz *= 2;
  for (int i = 0; i < N; ++i)
    arbInt[i + arbSz - 1] = 1;
  for (int i = arbSz - 2; i >= 0; --i)
    arbInt[i] = arbInt[leftSon(i)] + arbInt[rightSon(i)];
}

void update(int pos, int delta) {
  pos += arbSz - 1;
  while (pos >= 0) {
    arbInt[pos] += delta;
    pos = parent(pos);
  }
}

int kthElement(int k) {
  int cur = 0;
  while (cur < arbSz - 1) {
    if (arbInt[leftSon(cur)] <= k) {
      k -= arbInt[leftSon(cur)];
      cur = rightSon(cur);
    }
    else cur = leftSon(cur);
  }
  return cur - (arbSz - 1);
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  LL K;
  scanf("%d%lld", &N, &K);
  pre();
  for (int i = 0; i < N; ++i) {
    int r = N - i;
    LL p = 1LL * (r - 2) * (r - 1) / 2;
    int ith = 0;
    if (p < K) {
      ith = (int)(K - p);
      K -= ith;
    }
    int true_ith = kthElement(ith);
    update(true_ith, -1);
    printf("%d ", true_ith + 1);
  }
  putchar('\n');
  return 0;
}