#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
map<ll, int> mp;
map<ll, int> q;
int solve(ll n) {
if (n == 1) {
return 0;
}
if (mp.count(n)) {
return mp[n];
}
if (n % 2 == 0) {
return mp[n] = solve(n / 2) + 1;
}
mp[n] = solve(n / 2) + 2;
if (n % 3 == 0) {
int x = solve(n / 3) + 2;
if (x < mp[n]) {
mp[n] = x;
q[n] = 1;
}
} else {
int x = solve(n / 3) + 3;
if (x < mp[n]) {
mp[n] = x;
q[n] = 1;
}
}
return mp[n];
}
vector<int> construct_permutation(ll k) {
solve(k);
vector<int> t;
while (k > 1) {
if (!q[k]) {
t.push_back(-2 + k % 2);
k /= 2;
} else {
t.push_back(k % 3);
k /= 3;
}
}
vector<int> ans;
int v = 0, u = -1;
for (int i = t.size() - 1; i >= 0; i--) {
if (t[i] == -2) {
ans.push_back(v++);
} else if (t[i] == -1) {
ans.push_back(v++);
ans.push_back(u--);
} else if (t[i] == 0) {
ans.push_back(v + 1);
ans.push_back(v);
v += 2;
} else if (t[i] == 1) {
ans.push_back(v + 1);
ans.push_back(v);
ans.push_back(u--);
v += 2;
} else {
ans.push_back(v + 1);
ans.push_back(u--);
ans.push_back(v);
v += 2;
}
}
int add = -*min_element(ans.begin(), ans.end());
for (int &x : ans) {
x += add;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
11 ms |
1492 KB |
Output is correct |
6 |
Correct |
14 ms |
1872 KB |
Output is correct |
7 |
Correct |
20 ms |
2968 KB |
Output is correct |
8 |
Correct |
31 ms |
4332 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
32 ms |
4356 KB |
Output is correct |
12 |
Correct |
27 ms |
3704 KB |
Output is correct |
13 |
Partially correct |
30 ms |
3788 KB |
Partially correct |