Submission #710003

#	Time	Username	Problem	Language	Result	Execution time	Memory
710003		Astrayt	Permutation (APIO22_perm)	C++17	91.33 / 100	3 ms	392 KiB

perm

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back

vector<int> construct_permutation(ll k){
    int len = 1;
    while((1ll << len) < k) len++;
    vector<int> ans, tmp;
    for(int i = 1; i < len; ++i){
        ans.pb(2 * i);
    }
    k -= (1ll << (len - 1));
    for(int cur = 2 * len - 1, pw = 0; cur >= 1; cur -= 2, pw++){
        if(k & (1ll << pw)) tmp.pb(cur);
    }
    for(auto x:ans) tmp.pb(x);
    swap(ans, tmp);
    vector<int> ls = ans;
    sort(ls.begin(), ls.end());
    for(auto &x:ans){
        x = lower_bound(ls.begin(), ls.end(), x) - ls.begin();
    }
    return ans;
}

/*
int main(){
    int q; cin >> q;
    while(q--){
        int k; cin >> k;
        vector<int> v = construct_permutation(k);
        for(auto x:v) cout << x << ' ';
        cout << '\n';
    }
}
*/

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