QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622684#7778. Turning Permutationphuong2222WA 1ms3732kbC++141.7kb2024-10-09 00:02:442024-10-09 00:02:46

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 00:02:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3732kb
  • [2024-10-09 00:02:44]
  • 提交

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
    {
        for (int i = n;i >= 1;--i)
        {
            lli sum = 0;
            for (int j = 1;j <= n;++j)
            {
                sum += dp[i][j][1] + dp[i][j][0];
                if (sum >= k)
                {
                    cout << v[j - 1] << " ";
                    swap(v[j - 1],v.back());
                    v.pop_back();
                    sort(v.begin(),v.end());
                    k = k - sum;
                    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: 3660kb

input:

3 2

output:

2 1 3 

result:

ok 3 number(s): "2 1 3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3732kb

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3688kb

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: 3608kb

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3672kb

input:

3 1

output:

1 2 3 

result:

wrong answer 2nd numbers differ - expected: '3', found: '2'