solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

const int maxn = 10;
long long fact[maxn];
void init() {
    fact[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fact[i] = fact[i - 1] * i;
    }
}

class Solution {
   public:
    string getPermutation(int n, int k) {
        init();
        k--;
        vector<int> rest(n, 0);
        iota(rest.begin(), rest.end(), 1);
        vector<int> A(n + 1);
        for (int i = 1; i <= n; i++) {
            A[i] = k / fact[n - i];
            k = k % fact[n - i];
        }
        debug(A);
        for (int i = 1; i <= n; i++) {
            A[i] = rest[A[i]];
            rest.erase(lower_bound(rest.begin(), rest.end(), A[i]));
        }
        debug(A);
        string ans = "";
        for (int i = 1; i <= n; i++) {
            ans += '0' + A[i];
        }
        return ans;

    }
};