| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 623812 | iomoon191 | Permutation (APIO22_perm) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <perm.h>
using ll = long long;
#define int ll
using namespace std;
#define sz(x) (int)(x).size()
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define mod 998244353
#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"
using vi = vector<int>;
using pi = pair<int, int>;
const ll N = 200005;
const ll inf = 1e18;
vi construct_permutation(int k){
if(k == 1) return {};
if(k == 2) return {0};
if(k == 3) return {1, 0};
vi d = construct_permutation(k >> 2);
int s = sz(d);
if(k % 4 == 0){
d.push_back(s);
d.push_back(s + 1);
return d;
}
if(k % 4 == 1){
d.push_back(s);
d.push_back(s + 1);
d.push_back(-1);
for(auto i : d) i++;
return d;
}
if(k % 4 == 2){
d.push_back(s);
d.push_back(-1);
d.push_back(s + 1);
for(auto i : d) i++;
return d;
}
if(k % 4 == 3){
vi _d = d;
d.push_back(s);
d.push_back(s + 1);
for(auto i : d) if(i > 1) i++;
d.push_back(2);
vi f(sz(d));
int sum = 1;
foru(i, 0, sz(d) - 1){
f[i] = 1;
foru(j, 0, i - 1){
if(d[j] < d[i]) f[i] += f[j];
f[i] = min(f[i], inf);
}
sum += f[i];
sum = min(sum, inf);
}
if(sum == k) return d;
for(auto i : _d) i += 2;
_d.push_back(s + 2);
_d.push_back(1);
_d.push_back(s + 3);
_d.push_back(0);
return _d;
}
}