QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #622699 | #7778. Turning Permutation | phuong2222 | WA | 1ms | 3744kb | C++14 | 3.1kb | 2024-10-09 00:24:11 | 2024-10-09 00:24:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const int maxN = 55;
lli dp[maxN][maxN][2],n,k;
void input()
{
cin >> n >> k;
}
vector<int> v;
lli calc(int n)
{
if (n == 1) return 1;
lli res = 0;
for (int j = 1;j <= n;++j)
res += dp[n][j][0] + dp[n][j][1];
return res;
}
void solve()
{
dp[1][1][0] = dp[1][1][1] = 1;
for (int i = 2;i <= n;++i)
{
for (int j = 1;j <= i;++j)
{
dp[i][j][0] = 0;
dp[i][j][1] = 0;
for (int k = j;k < i;++k)
{
//cout << k << "a\n";
dp[i][j][0] += dp[i - 1][k][1];
}
//cout << j << "A\n";
for (int k = j - 1;k >= 1;--k)
{
//cout << k << "b\n";
dp[i][j][1] += dp[i - 1][k][0];
}
}
}
for (int i = 1;i <= n;++i) v.push_back(i);
if (calc(n) < k) cout << -1;
else
{
int flag = 0,pre = n + 1;
for (int i = n;i >= 1;--i)
{
//cout << i << " " << flag << "\n";
lli sum = 0;
if (flag == 0)
{
for (int j = 1;j <= i;++j)
{
sum += dp[i][j][1] + dp[i][j][0];
//cout << k << " " << sum << " " << i << " " << j << "\n";
if (sum >= k)
{
cout << v[j - 1] << " ";
swap(v[j - 1],v.back());
v.pop_back();
sort(v.begin(),v.end());
if (sum - dp[i][j][0] >= k) k = k - sum + dp[i][j][0];
else
{
k = k - sum + dp[i][j][0] + dp[i][j][1];
flag = 1;
}
//cout << i << " " << dp[i][j][0] << " " << dp[i][j][1] << "\n";
pre = j;
break;
}
}
}
else
{
for (int j = n;j > pre;--j)
{
sum += dp[i][j][1] + dp[i][j][0];
//cout << k << " " << sum << " " << i << " " << j << "\n";
if (sum >= k)
{
cout << v[j - 1] << " ";
swap(v[j - 1],v.back());
v.pop_back();
sort(v.begin(),v.end());
if (sum - dp[i][j][0] >= k)
{
k = k - sum + dp[i][j][0];
flag = 0;
}
else k = k - sum + dp[i][j][0] + dp[i][j][1];
pre = j;
break;
}
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("P2.inp","r",stdin);
// freopen("P2.out","w",stdout);
input();
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
4 6
output:
3 1 2 4
result:
ok 4 number(s): "3 1 2 4"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
3 1
output:
1 3 2
result:
ok 3 number(s): "1 3 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
3 10
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 52
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
3 756
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 7721
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: -100
Wrong Answer
time: 1ms
memory: 3676kb
input:
5 1
output:
1 5 2 3 4
result:
wrong answer 2nd numbers differ - expected: '3', found: '5'