Submission #731796

#	Time	Username	Problem	Language	Result	Execution time	Memory
731796		hoainiem	Permutation (APIO22_perm)	C++17	91.33 / 100	3 ms	340 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
long long k, sum = 1;
vector<long long>f;
vector<int> ans;
long long get(long long cur, long long x){
    if (x >= 60)
        return 1LL << 60;
    if (k / cur < (1 << x))
        return cur * (1 << x);
    return 1LL << 60;
}
std::vector<int> construct_permutation(long long K){
    ans.clear();
    f.clear();
    k = K;
    f.push_back(1);
    ans.push_back(0);
    sum = 1;
    for (int i = 1; sum < k; i++){
        if (sum * 2 <= k){
            ans.push_back(i);
            f.push_back(sum);
            sum <<= 1;
            continue;
        }
        for (long long j = (int)f.size() - 1, d = sum; j > 0; j--){
            d -= f[j];
            if (sum + d <= k){
                sum += d;
                ans.insert(ans.begin() + j, i);
                f.insert(f.begin() + j, d);
                break;
            }
        }
    }
    ans.erase(ans.begin());
    for (int i = 0; i < (int)ans.size(); i++)
        ans[i]--;
    return ans;
}

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