Submission #1061199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061199		stdfloat	Permutation (APIO22_perm)	C++17	63.80 / 100	10 ms	1628 KiB

perm

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

using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //mt19937_64 for ll

int rnd(int l, int r) {
    return l + rng() % (r - l + 1);
}

vector<int> construct_permutation(ll k) {
    k--;

    int sm = -1;
    vector<int> v;
    while (k) {
        int x = __lg(k + 1);

        if (x && (rnd(0, 1) & 1)) x--;
        
        sm += x;
        v.push_back(x);
        
        k -= (1LL << x) - 1;
    }

    vector<int> ans;
    for (int i = 0; i < (int)v.size(); i++) {
        for (int j = sm - v[i] + 1; j <= sm; j++) {
            ans.push_back(j);
        }

        sm -= v[i];
    }

    return ans;
}

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