QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#280899 | #7778. Turning Permutation | ucup-team1191# | WA | 0ms | 3868kb | C++23 | 3.4kb | 2023-12-09 18:20:04 | 2023-12-09 18:20:04 |
Judging History
answer
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
const ll Inf = (ll)1e18 + 7;
const int N = 50;
ll dp[N][2][2]; // 1 - up, 0 - down
ll safe_mul(ll a, ll b) {
if (b == 0)
return 0;
if (a > Inf / b) {
return Inf;
}
return min(Inf, a * b);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
ll k;
cin >> n >> k;
--k;
vector<vector<ll>> C(n + 1, vector<ll>(n + 1));
for (int i = 0; i <= n; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
C[i][j] = min(C[i][j], Inf);
}
}
dp[1][0][1] = dp[1][1][0] = 1;
for (int len = 2; len <= n; ++len) {
for (int lf = 0; lf <= 1; ++lf) {
for (int rg = 0; rg <= 1; ++rg) {
for (int pos = 0; pos < len; ++pos) {
if (pos == 0 && lf == 0)
continue;
if (pos == len - 1 && rg == 1)
continue;
ll ways = 1;
int lf_sz = pos;
int rg_sz = len - pos - 1;
if (lf_sz > 0)
ways = safe_mul(ways, dp[lf_sz][lf][1]);
if (rg_sz > 0)
ways = safe_mul(ways, dp[rg_sz][0][rg]);
ways = safe_mul(ways, C[lf_sz + rg_sz][lf_sz]);
dp[len][lf][rg] += ways;
dp[len][lf][rg] = min(dp[len][lf][rg], Inf);
}
}
}
}
for (int i = 1; i <= n; ++i) {
for (int lf = 0; lf <= 1; ++lf) {
for (int rg = 0; rg <= 1; ++rg) {
// cout << i << ' ' << lf << ' ' << rg << ' ' << dp[i][lf][rg] << endl;
}
}
}
{
ll tot = 0;
for (int i = 0; i <= 1; ++i) {
for (int j = 0; j <= 1; ++j) {
tot += dp[n][i][j];
tot = min(tot, Inf);
}
}
if (tot <= k) {
cout << "-1\n";
return 0;
}
}
vector<int> used(n), p(n), ip(n, -1);
for (int i = 0; i < n; ++i) {
auto calc_ways = [&]() {
vector<int> lens;
ll ways = 1;
for (int l = 0; l < n; ++l) {
if (ip[l] == -1) {
int r = l;
while (r < n && ip[r] == -1) {
++r;
}
--r;
lens.push_back(r - l + 1);
ll cur = 0;
for (int lf = 0; lf <= 1; ++lf) {
for (int rg = 0; rg <= 1; ++rg) {
if (l != 0 && lf == 0)
continue;
if (r + 1 != n && rg == 1)
continue;
cur += dp[r - l + 1][lf][rg];
cur = min(cur, Inf);
}
}
ways = safe_mul(ways, cur);
l = r;
}
}
int rem = 0;
for (auto l : lens) {
rem += l;
ways = safe_mul(ways, C[rem][l]);
}
return ways;
};
for (int j = 0; j < n; ++j) {
if (used[j])
continue;
p[i] = j;
ip[j] = i;
used[j] = 1;
ll ways = calc_ways();
if (ways > k) {
break;
}
k -= ways;
p[i] = 0;
ip[j] = -1;
used[j] = 0;
}
}
for (int i = 0; i < n; ++i) {
cout << p[i] + 1 << ' ';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
4 6
output:
3 1 2 4
result:
ok 4 number(s): "3 1 2 4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3792kb
input:
3 1
output:
1 2 3
result:
wrong answer 2nd numbers differ - expected: '3', found: '2'