Submission #573133

#	Time	Username	Problem	Language	Result	Execution time	Memory
573133		dqhungdl	Permutation (APIO22_perm)	C++17	71.22 / 100	12 ms	1108 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
using namespace std;

int pivot;
vector<int> rs;

void backtrack(long long k) {
    if (!k)
        return;
    long long pw2 = 1, cnt = 0;
    while (pw2 * 2 - 1 <= k) {
        pw2 *= 2;
        cnt++;
    }
    for (int i = pivot - cnt + 1; i <= pivot; i++)
        rs.push_back(i);
    pivot -= cnt;
    backtrack(k - pw2 + 1);
}

std::vector<int> construct_permutation(long long k) {
    pivot = 1e9;
    rs.clear();
    backtrack(k - 1);
    int minVal = *min_element(rs.begin(), rs.end());
//    cout << minVal << '\n';
//    for (int &x: rs)
//        cout << x << ' ';
//    cout << '\n';
    for (int &x: rs)
        x -= minVal;
    return rs;
}

• Subtask 1: 10 / 10
• Subtask 2: 61.215384618 / 90