| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1344522 | omarrrr | Permutation (APIO22_perm) | C++20 | 0 ms | 0 KiB |
#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> construct_permutation(long long k) {
// The empty array naturally has 1 subsequence (the empty one)
if (k == 1) return {};
// Find the maximum m such that 3^m <= k
long long m = 0;
long long p3 = 1;
while (p3 * 3 <= k) {
p3 *= 3;
m++;
}
vector<long long> temp;
// 1. BACKBONE: Multiply by 3
// Each block of (10i+1, 10i) multiplies the total subsequences by 3
for (long long i = 0; i < m; i++) {
temp.push_back(10LL * i + 1);
temp.push_back(10LL * i);
}
// 2. ADDITIONS: Process the remainder in Base-3
long long R = k - p3;
for (long long p = m; p >= 0; p--) {
long long current_p3 = 1;
for (int i = 0; i < p; i++) current_p3 *= 3;
long long digit = R / current_p3;
R %= current_p3;
// By appending at the very end with a value of 10p - 5,
// the element is perfectly sandwiched between block p-1 and block p.
if (digit == 1) {
temp.push_back(10LL * p - 5);
}
// To add 2 without cross-multiplying, we append two elements in decreasing order
else if (digit == 2) {
temp.push_back(10LL * p - 4);
temp.push_back(10LL * p - 5);
}
}
// 3. COORDINATE COMPRESSION
// Map our widely spaced raw values down to a strict 0 to N-1 sequence
vector<long long> sorted_temp = temp;
sort(sorted_temp.begin(), sorted_temp.end());
vector<int> res;
for (long long val : temp) {
int rank = lower_bound(sorted_temp.begin(), sorted_temp.end(), val) - sorted_temp.begin();
res.push_back(rank);
}
return res;
}
int main() {
long long k;
if (cin >> k) {
vector<int> v = construct_permutation(k);
cout << v.size() << "\n";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << (i == v.size() - 1 ? "" : " ");
}
cout << "\n";
}
return 0;
}