Submission #979082

#	Time	Username	Problem	Language	Result	Execution time	Memory
979082		sunnat	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	604 KiB

perm

#include <iostream>
#include <vector>
using namespace std;

vector<int> construct_permutation(long long k){
    vector<int> a;
    while((1ll<<a.size()) <= k) a.push_back(a.size());
    a.pop_back();
    k -= 1LL<<a.size();
    if(k > 0){
        int bt = 60;
        while(!((k >> bt)&1)) --bt;
        for(int &x:a) if(x >= bt) ++ x;
        a.push_back(bt);
        k -= 1LL<<bt --;
        while(bt >= 0){
            if(bt > 0 && (k>>(bt-1)) == 3){
                --bt;
                for(int &x:a) if(x >= bt) ++ x;
                a.insert(a.end() - 2, bt);
                k -= 3LL<<bt--;
            }
            else if((k >> bt) == 1){
                for(int &x:a) if(x >= bt) ++x;
                a.push_back(bt);
                k -= 1LL<<bt--;
            }
            else bt --;
        }
    }
    return a;
}

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