Submission #979062

#	Time	Username	Problem	Language	Result	Execution time	Memory
979062		sunnat	Permutation (APIO22_perm)	C++17	91.33 / 100	745 ms	672 KiB

perm

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

vector<int> construct_permutation(long long k){
    --k;
    int val = 0;
    vector<int> a;
    vector<long long> lstdp;
    long long sum = 0;
    auto calc = [&](){
        sum = 0;
        lstdp.resize(a.size());
        for(int i = 0; i < lstdp.size(); ++ i){
            lstdp[i] = 1;
            for(int j = 0; j < i; ++ j)
                if(a[i] > a[j]) lstdp[i] += lstdp[j];
            sum += lstdp[i];
        }
        return sum;
    };
    while(sum != k){
        a.push_back(a.size());
        int i = a.size() - 1;
        while(calc() > k){
            swap(a[i], a[i-1]);
            --i;
        }
    }
    return a;
}

Compilation message (stderr)

perm.cpp: In lambda function:
perm.cpp:14:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         for(int i = 0; i < lstdp.size(); ++ i){
      |                        ~~^~~~~~~~~~~~~~
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:7:9: warning: unused variable 'val' [-Wunused-variable]
    7 |     int val = 0;
      |         ^~~

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