Submission #1177380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177380		anmattroi	Permutation (APIO22_perm)	C++17	91.33 / 100	2 ms	328 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>

using namespace std;

template <class T> vector<int> compress(vector<T> a) {
    int N = a.size();
    vector<T> b(a.begin(), a.end());
    sort(b.begin(), b.end());
    vector<int> ans;
    for (T i : a) ans.emplace_back(lower_bound(b.begin(), b.end(), i) - b.begin());
    return ans;
}


vector<int> construct_permutation(long long k) {
    int o = __lg(k), cnt = __builtin_popcountll(k);

    vector<double> ans;
    for (int i = 1; i <= o; i++) ans.emplace_back(i);
    for (int64_t i = o-1; i >= 0; i--)
        if (k>>i&1LL) ans.emplace_back(((i == 0 ? 0 : ans[i-1]) + ans[i]) * 0.5);


    return compress(ans);


}

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