Submission #838269

#	Time	Username	Problem	Language	Result	Execution time	Memory
838269		ngano_upat_na	Permutation (APIO22_perm)	C++17	10 / 100	1 ms	340 KiB

perm

#include "bits/stdc++.h"
#include "perm.h"
using namespace std;
using ll = long long;

vector<int> construct_permutation(long long k) {
    ll n = k;
    vector<int> ans;
    if (n <= 90) {
        for (int i=n-2; i>=0; i--) {
            ans.push_back(i);
        }   
        return ans;
    }   
    ll main_cap = 0, index = 0;
    for (ll i=0; ; i++) {
        ll a = (1LL << i);
        if (a <= n) {
            main_cap = a;
            index = i;
        }   
        else {
            break;
        }   
    }   
    for (int i=0; i<index-1; i++) {
        ans.push_back(i);
    }   
    int cur = index-1;
    n -= main_cap;
    
    while (true) {
        if (n == 0) {
            return ans;
        }   
        vector<int> A;
        main_cap = 0, index = 0;
        for (ll j=0; ; j++) {
            ll a = (1LL << j);
            if (a <= n) {
                main_cap = a;
                index = j;
            }   
            else {
                break;
            }   
        }   
        bool added = false;
        index--;
        for (auto &e:ans) {
            if (e > index) {
                if (!added) {
                    A.push_back(cur);
                    A.push_back(e);
                    added = true;
                }   
                else {
                    A.push_back(e);
                }   
            }   
            else {
                A.push_back(e);
            }   
        }   
        ans = A;
        cur++;
        n -= main_cap;
    }   
    return ans;
}    

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