My Solution
```
/**
 * Time Complexity: O(n * n)
 * Space Complexity: O(n)
 */
class Solution {
 public:
  vector<int> permute(const int n, const long long k) {
    long long counts[n + 1];
    counts[0] = 1;
    for (int i = 1; i < n + 1; ++i) {
      if (counts[i - 1] > k) {
        counts[i] = counts[i - 1];
      } else {
        counts[i] = counts[i - 1] * ((i + 1) >> 1);
      }
    }

    if (((n & 1) == 1 && k > counts[n]) ||
        ((n & 1) == 0 && k > (counts[n] << 1))) {
      return {};
    }

    vector<int> ret(n);
    long long remained = k - 1;
    if ((n & 1) == 0) {
      // `n` is even,
      // the first element of the result permutation can be an odd integer or an even integer
      ret.front() = 1 + (remained / counts[n - 1]);
    } else {
      // `n` is odd,
      // the first element of the result permutation must be an odd integer
      ret.front() = 1 + ((remained / counts[n - 1]) << 1);
    }
    remained %= counts[n - 1];
    bool occupied[n];
    memset(occupied, 0, sizeof(occupied));
    occupied[ret.front() - 1] = true;
    int8_t parity = (ret.front() & 1) ^ 1;
    for (int i = 2; i < n + 1; ++i) {
      const int target_index = remained / counts[n - i];
      remained %= counts[n - i];
      for (int index = -1, candidate = 1; candidate < n + 1; ++candidate) {
        if ((candidate & 1) == parity &&
            !occupied[candidate - 1] &&
            ++index == target_index) {
          ret[i - 1] = candidate;
          occupied[candidate - 1] = true;
          break;
        }
      }
      parity ^= 1;
    }
    return ret;
  }
};
```
['C++']