Submission #1003478

#TimeUsernameProblemLanguageResultExecution timeMemory
1003478mispertionPermutation (APIO22_perm)C++17
91.33 / 100
391 ms596 KiB
#include "perm.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define sz(x) (int)x.size() #define pb(x) push_back(x) ll calcperm(vector<int> a){ vector<ll> dp(sz(a)); ll ans = 1; for(int i = 0; i < sz(a); i++){ dp[i] = 1; for(int j = i - 1; j >= 0; j--){ if(a[i] > a[j]) dp[i] += dp[j]; } ans = ans + dp[i]; } return ans; } vector<int> construct_permutation(long long k){ vector<int> ans = {}; ll cur = 0; while(cur < k){ ans.insert(ans.begin(), sz(ans)); int rem = 0; for(; rem < sz(ans); rem++){ vector<int> ch = {}; ch.pb(sz(ans) - rem - 1); for(int i = 1; i < sz(ans); i++){ if(ans[i] >= sz(ans) - rem - 1) ch.pb(ans[i] + 1); else ch.pb(ans[i]); } if(calcperm(ch) > k) break; } rem--; ans[0] -= rem; for(int i = 1; i < sz(ans); i++) if(ans[i] >= ans[0]) ans[i]++; cur = calcperm(ans); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...