제출 #1164072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164072		just	Permutation (APIO22_perm)	C++20	64.63 / 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;
    // }

    vec<int> pows;
    int sum = 0;
    for(int i = 0; i < 62; i++) {
        if (k & (1LL << i)) {
            pows.push_back(i);
            sum += i;
        }
    }

    int n = sum + pows.size() - 1;
    
    vec<int> ans(n);
    iota(all(ans), 0);

    int cur = pows.size() - 1;
    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 = 1; k <= 1000; k++) {
        vec<signed> ans = construct_permutation(k);
        for(int i = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
        }
        cout << endl;
    }
}
#endif

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