Submission #1225302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225302		SpyrosAliv	Permutation (APIO22_perm)	C++20	91.33 / 100	1 ms	328 KiB

perm

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

const int LOG = 64;

vector<int> construct_permutation(ll k) {
    k--;
    vector<int> perm;
    vector<int> bits;
    ll curr = 0;
    for (int i = 0; i < LOG; i++) {
        curr |= (1LL << i);
        if (k >= curr) {
            bits.push_back(i);
        }
        else break;
    }
    //curr /= 2;
    //k -= curr;
    if (k == curr/2) {
        return bits;
    }
    vector<int> after;
    bool flag = false;
    for (int i = LOG-1; i >= 0; i--) {
        if (!((k >> i) & 1)) continue;
        if (!flag) {
            flag = true;
        }
        else {
            for (int j = 0; j < (int)bits.size(); j++) {
                if (bits[j] >= i) bits[j]++;
            }
            bits.push_back(i);
        }
    }
    for (auto &x: bits) x++;
    bits.push_back(0);
    return bits;
}

bool check(vector<int> a, ll x) {
    x--;
    int n = a.size();
    vector<ll> dp(n, 0);
    dp[0] = 1;
    x--;
    for (int i = 1; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] += dp[j];
            }
        }
        x -= dp[i];
    }
    if (x == 0) return true;
    else return false;
}

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