이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
* TASK: ROS/cdgp001/Increasing subsequences
* solution 3/2 log n
* Author: Karol Pokorski
*/
#include <bits/stdc++.h>
#include "perm.h"
using namespace std;
typedef long long int LL;
void apply_gadget(vector<int>& v,
const vector<int>& gadget) {
vector<int> gadget_items;
for (int x : gadget) if (x > 0) gadget_items.push_back(x);
sort(gadget_items.begin(), gadget_items.end());
for (int x : gadget_items)
for (int& y : v)
if (y >= x) y++;
int n_size = v.size() + gadget.size();
for (int x : gadget) {
if (x <= 0) v.push_back(n_size + x);
else v.push_back(x);
}
}
vector<int> dec2bin(LL x) {
vector<int> result;
while (x > 0) { result.push_back(x % 2); x /= 2; }
reverse(result.begin(), result.end());
return result;
}
vector<int> permutation(LL k) {
if (k == 1) return vector<int>();
if (k == 2) return vector<int>({1});
if (k == 3) return vector<int>({2, 1});
vector<int> bin_k = dec2bin(k);
vector<int> result;
int p = 1;
if (bin_k[p] == 0) {
if (bin_k[p+1] == 0) result = vector<int>({3, 2, 1});
if (bin_k[p+1] == 1) result = vector<int>({2, 3, 1});
p += 2;
}
else { result = vector<int>({2, 1}); p++; }
while (p+1 < (int)bin_k.size()) {
if (bin_k[p] == 0) {
apply_gadget(result, vector<int>({0}));
p++;
}
else {
if (bin_k[p+1] == 0)
apply_gadget(result, vector<int>({-1, 1, 0}));
else
apply_gadget(result, vector<int>({-1, 0, 3}));
p += 2;
}
}
if (p < (int)bin_k.size()) {
if (bin_k[p] == 0)
apply_gadget(result, vector<int>({0}));
if (bin_k[p] == 1)
apply_gadget(result, vector<int>({0, 1}));
p++;
}
return result;
}
vector<int> construct_permutation(long long k) {
vector<int> result = permutation(k);
for(int i=0;i<result.size();i++)
result[i]--;
return result;
}
컴파일 시 표준 에러 (stderr) 메시지
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0;i<result.size();i++)
| ~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |