제출 #718368

#제출 시각아이디문제언어결과실행 시간메모리
718368lam순열 (APIO22_perm)C++17
10 / 100
1 ms340 KiB
#include "perm.h" #include <bits/stdc++.h> #define ll long long using namespace std; long long count_inc(const vector<int>& v) { vector<long long> dp(v.size() + 1, 0); dp[0] = 1; for (int x : v) { for (int i = 0; i <= x; i++) { dp[x+1] += dp[i]; dp[x+1] = min(dp[x+1],(ll)1e18+1); } } long long result = 0; for (int i = 0; i <= (int)v.size(); i++){ result += dp[i]; result = min(result,(ll)1e18+1); } return result; } vector<int> construct_permutation(long long k) { ll kk = k; vector <int> res; ll len = log2(k); vector <int> a; for (int i=1; i<=len; i++) a.push_back(i-1); k-=(1LL<<len); while (k>0) { ll it = 0; while ((1LL<<(it+1))<= k) { it++; } k-= (1LL<<it); a.push_back(it); } int n=a.size(); vector <int> d(n+1,0); for (int i=0; i<n; i++) d[a[i]] ++; for (int i=1; i<=n; i++) d[i]+=d[i-1]; res.resize(n); for (int i=0; i<n; i++) res[i] = --d[a[i]]; // for (int i:a) cerr<<i<<' '; cerr<<endl; // for (int i:res) cerr<<i<<' '; cerr<<endl; vector <int> v=res; sort(v.begin(),v.end()); for (int i=0; i<n; i++) assert(v[i]==i); ll ttemp = count_inc(res); assert(ttemp==kk); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...