Cod sursă (job #785004)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("arbperm.in");
ofstream fout("arbperm.out");

int n, k;
const int NMAX = 100000;
int v[NMAX + 5];

int main() {
    int aux, maxi = 0, fact = 1, gasit;
    fin >> n >> k;

    vector<int> a;

    // Reading the array and finding the position of the maximum element (n)
    for (int i = 0; i < n; ++i) {
        fin >> aux;
        if (aux == n) {
            maxi = i; // Save the position of the maximum element
        }
        a.push_back(aux); // Store the elements in the vector 'a'
    }

    fact *= a.size(); // Initialize factorial with the size of the array
    int ramase = a.size() - maxi - 1; // Elements remaining after the maximum position

    // cout << a.size() << " " << maxi << " " << ramase << "\n"; // Debug info
    // cout << ramase << "\n"; // Debug info
    gasit = ramase;
    v[a.size() - 1] = ramase;

    // Removing the maximum element from the vector 'a'
    a.erase(a.begin() + maxi);

    // for (int elem : a) { cout << elem << " "; } // Debug info
    // cout << "\n\n"; // Debug info

    int last_maxi, trecute = 0;

    // Loop to calculate permutations while ramase <= k
    while (ramase <= k) {
        // Find the new position of the maximum element
        for (int i = 0; i < a.size(); ++i) {
            if (a[i] == a.size()) {
                maxi = i;
            }
        }
        last_maxi = maxi;

        // cout << a.size() << " " << maxi << " " << ramase << "\n"; // Debug info

        ramase += (a.size() - maxi - 1) * fact; // Update ramase with the permutations count
        v[a.size() - 1] = (a.size() - maxi - 1) * fact;
        trecute += v[a.size()];

        fact *= a.size(); // Update factorial for the next iteration
        // cout << "fact " << fact << "\n"; // Debug info
        // cout << ramase << "\n"; // Debug info

        a.erase(a.begin() + maxi); // Remove the maximum element again

        // for (int elem : a) { cout << elem << " "; } // Debug info
        // cout << "\n\n"; // Debug info
    }

    // Debug output for the array 'v' and other values
    // for (int i = 0; i < 10; ++i) { cout << v[i] << " "; }
    // cout << "\n" << last_maxi << " " << trecute << "\n\n";

    k -= trecute;
    // cout << k << "\n\n\n"; // Debug info

    // Compute factorial values and store them in 'fct' array
    vector<int> fct(n + 1);
    aux = 1;
    int pas = n;
    for (int i = n; i > 0; --i) {
        fct[i] = aux;
        aux = aux * pas;
        pas--;
    }

    // Debug output for the factorial array 'fct'
    // for (int i = 0; i <= n; ++i) { cout << fct[i] << " "; }
    // cout << "\n\n";

    // cout << a.size() << "\n\n"; // Debug info

    bool GATA = 1;
    // Inserting elements into 'a' until it matches the desired condition
    for (int i = last_maxi + 1; i <= a.size() && a.size() < n - 1; ++i) {
        a.insert(a.begin() + i, a.size() + 1);

        // Debug output for the updated array 'a'
        // for (int elem : a) { cout << elem << " "; }
        // cout << "\n\n";

        // cout << "size " << a.size() << " k " << k << fct[a.size()] << "\n\n"; // Debug info
        if (fct[a.size()] >= k) {
            while (a.size() < n - 1) {
                int ok = 1;
                for (int j = 0; j <= a.size() && a.size() < n - 1; ++j) {
                    if (fct[a.size() + 1] >= k) {
                        a.insert(a.begin() + j, a.size() + 1);

                        // Debug output for size and updated array 'a'
                        // cout << "size:" << a.size() << "\n";
                        // for (int elem : a) { cout << elem << " "; }
                        // cout << "\n\n";

                        if (a.size() >= n - 1) {
                            GATA = 0;
                            ok = 0;
                        }
                    } else {
                        k -= fct[a.size() + 1];
                    }
                }
            }
        } else {
            a.erase(a.begin() + i);
            k -= fct[a.size()];
        }
    }

    // Final insertion into the array 'a'
    a.insert(a.begin() + k - 1, a.size() + 1);

    // Output the result to the output file
    for (int elem : a) {
        fout << elem << " ";
    }
    fout << "\n\n";
    return 0;
}