# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
993598 | 2024-06-06T06:27:53 Z | abczz | 순열 (APIO22_perm) | C++17 | 25 ms | 472 KB |
#include "perm.h" #include <iostream> #define ll long long using namespace std; vector <int> base2(ll k) { vector <int> V; ll mxbit = 0, cnt = 0; for (int i=59; i>=0; --i) { if (k & (1LL<<i)) { mxbit = i; break; } } for (int j=0; j<mxbit; ++j) { if (k & (1LL<<j)) V.push_back(-1); V.push_back(++cnt); } ll x = V.size(); for (auto &u : V) { if (u == -1) u = x--; --u; } return V; } vector <int> base3(ll k) { vector <int> V, U; ll cnt = 0; ll tmp = k; while (tmp) { U.push_back(tmp % 3); tmp /= 3; } for (int i=0; i+1<U.size(); ++i) { if (U[i] == 1) V.push_back(-1); V.push_back(cnt+2); if (U[i] == 2) V.push_back(-1); V.push_back(cnt+1); cnt += 2; } if (U.back() == 2) V.push_back(++cnt); ll x = V.size(); for (auto &u : V) { if (u == -1) u = x--; --u; } return V; } vector<int> opt(ll k) { auto b2 = base2(k); auto b3 = base3(k); if (b2.size() < b3.size()) return b2; else return b3; } std::vector<int> construct_permutation(long long k) { auto f = opt(k); if (k <= 100) return f; for (int b=5; b<=100; ++b) { vector <int> pref = {}; if (k % b != 0) pref = opt((k % b) + 1); vector<int> bin = opt(b); vector<int> nx = opt(k/b); for (auto &u : nx) { u += (ll)bin.size(); } for (auto &u : pref) { u += (ll)(bin.size() + nx.size()); } if (f.size() > pref.size() + bin.size() + nx.size()) { f.clear(); for (auto u : pref) f.push_back(u); for (auto u : bin) f.push_back(u); for (auto u : nx) f.push_back(u); } } /*for (auto u : f) cout << u << " "; cout << endl;*/ return f; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 11 ms | 348 KB | Output is correct |
4 | Correct | 9 ms | 348 KB | Output is correct |
5 | Correct | 15 ms | 444 KB | Output is correct |
6 | Correct | 17 ms | 348 KB | Output is correct |
7 | Correct | 25 ms | 468 KB | Output is correct |
8 | Correct | 22 ms | 344 KB | Output is correct |
9 | Correct | 23 ms | 348 KB | Output is correct |
10 | Correct | 19 ms | 348 KB | Output is correct |
11 | Correct | 21 ms | 344 KB | Output is correct |
12 | Correct | 19 ms | 472 KB | Output is correct |
13 | Correct | 21 ms | 472 KB | Output is correct |