Submission #1164075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164075		just	Permutation (APIO22_perm)	C++20	71.22 / 100	7 ms	1096 KiB

perm

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

#define all(x) (x).begin(), (x).end()
#define vec vector
#define int long long

vec<int> solve(int k) {
    // if (k <= 90) {
    //     k--;
    //     vec<int> ans(k);
    //     iota(all(ans), 0);
    //     reverse(all(ans));
    //     return ans;
    // }

    // k--; // empty subsequence

    vec<int> pows; int sum = 0;
    for(int i = 62; i >= 1; i--) {
        int x = (1ll << i) - 1;
        while (k > x) {
            pows.push_back(i);
            sum += i;
            k -= x;
        }
    }

    int n = sum;
    
    vec<int> ans(n);
    iota(all(ans), 0);

    int cur = 0;
    for(int i = 0; i < pows.size(); i++) {
        reverse(ans.begin() + cur, ans.begin() + cur + pows[i]);
        cur += pows[i];
    }

    reverse(all(ans));

    return ans;
}

vec<signed> construct_permutation(int k) {
    vec<int> ans = solve(k);
    int n = ans.size();

    #ifdef debug
    vec<int> cnt(n);
    for(int i = 0; i < n; i++) {
        cnt[i] = 1;
        for(int j = 0; j < i; j++) {
            if (ans[j] < ans[i]) {
                cnt[i] += cnt[j];
            }
        }
    }
    
    int sum = 0;
    for(int i = 0; i < n; i++) {
        sum += cnt[i];
    }
    sum++;
    assert(sum == k);
    #endif

    vec<signed> res(n);
    for(int i = 0; i < n; i++) {
        res[i] = ans[i];
    }
    return res;
}

#ifdef debug
signed main() {
    for(int k = 2; k <= 10000; k++) {
        vec<signed> ans = construct_permutation(k);
        cout << k << ": ";
        for(int i = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
        }
        cout << endl;
    }
}
#endif

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