Submission #1366791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1366791		ezzzay	Permutation (APIO22_perm)	C++20	91.33 / 100	620 ms	496 KiB

perm

//#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
ll check(vector<int>a){
    int n=a.size();
    a.insert(a.begin(),0);
    vector<ll>dp(n+2);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<a[i];j++){
            if(dp[a[i]] > 2e18 - dp[j]){
                dp[a[i]]=2e18;
            }
            else dp[a[i]]+=dp[j];
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(ans>2e18-dp[i]){
            ans=2e18;
        }
        else ans+=dp[i];
    }
    return ans;
}
std::vector<int> construct_permutation(long long k){
    k--;
    vector<int>vc;
    while(k){
        int x=vc.size()+1;
        bool u=0;
        for(int i=vc.size();i>=0;i--){
            vc.insert(vc.begin()+i,x);
            if(check(vc)<=k){
                u=1;
                break;
            }
            vc.erase(vc.begin()+i);
        }
        if(u)continue;
        k-=check(vc);
        vector<int>pr;
        for(auto a:vc)pr.pb(a-1);
        return pr;
    }
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

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