# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
987606 | 2024-05-23T07:06:50 Z | Otalp | 순열 (APIO22_perm) | C++17 | 49 ms | 856 KB |
#include "perm.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back ll pref[200][200], suf[200][200]; ll a[200100]; ll n; void calc(){ for(int x=0; x<=n + 1; x++) pref[0][x] = 1; for(int i=1; i<=n; i++){ for(int x=0; x<=n + 1; x++){ pref[i][x] = pref[i - 1][x]; if(a[i] <= x){ pref[i][x] += pref[i-1][a[i]]; } } } for(int x=0; x<=n + 1; x++) suf[n + 1][x] = 1; for(int i=n; i>=1; i--){ for(int x=n + 1; x>=0; x--){ suf[i][x] = suf[i + 1][x]; if(a[i] >= x){ suf[i][x] += suf[i + 1][a[i]]; } } } } vector<int> construct_permutation(ll k){ n = 1; a[1] = 1; calc(); ll g = pref[n][n]; while(g != k){ ll d = 0; ll pos, x; for(int i=1; i<=n + 1; i++){ for(int j=1; j<=n+1; j++){ ll h = pref[i - 1][j - 1] * suf[i][j]; //cout<<i<<' '<<j<<'\n'; //cout<<h<<'\n'; if(h > d and h <= k - g){ d = h; x = j; pos = i; } } } //cout<<g<<' '<<pos<<' '<<x<<'\n'; vector<int> q; for(int i=1; i<pos; i++){ q.pb(a[i] + (a[i] >= x)); } q.pb(x); for(int i=pos; i<=n; i++){ q.pb(a[i] + (a[i] >= x)); } n ++; for(int i=1; i<=n; i++){ a[i] = q[i - 1]; } calc(); g = pref[n][n]; } vector<int> res; for(int i=1; i<=n; i++) res.pb(a[i]-1); //for(int d: res) cout<<d<<' '; //cout<<'\n'; return res; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 2 ms | 344 KB | Output is correct |
4 | Correct | 3 ms | 348 KB | Output is correct |
5 | Correct | 15 ms | 600 KB | Output is correct |
6 | Correct | 23 ms | 604 KB | Output is correct |
7 | Correct | 27 ms | 856 KB | Output is correct |
8 | Correct | 45 ms | 604 KB | Output is correct |
9 | Correct | 38 ms | 600 KB | Output is correct |
10 | Correct | 49 ms | 716 KB | Output is correct |
11 | Correct | 40 ms | 604 KB | Output is correct |
12 | Correct | 34 ms | 688 KB | Output is correct |
13 | Correct | 40 ms | 600 KB | Output is correct |