QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#291868#7778. Turning Permutationpengpeng_fudanWA 0ms3704kbC++141.3kb2023-12-27 10:39:252023-12-27 10:39:26

Judging History

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

  • [2023-12-27 10:39:26]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3704kb
  • [2023-12-27 10:39:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using ll=long long;
ll dp[60][60][2];//0向下1向上
ll pre[60][60][2];
int ans[60];
bool flag[60];
const ll inf=1e18;
void solve() {
    int n;ll k;
    cin>>n>>k;
    dp[1][1][1]=dp[1][1][0]=1;
    pre[1][1][1]=pre[1][1][0]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            dp[i][j][0]=min(inf,pre[i-1][j-1][1]);
            dp[i][j][1]=min(inf,pre[i-1][i-1][0]-pre[i-1][j-1][0]);
            pre[i][j][0]=min(inf,pre[i][j-1][0]+dp[i][j][0]);
            pre[i][j][1]=min(inf,pre[i][j-1][1]+dp[i][j][1]);
        }
    }
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=1;j<=n;j++){
            if(!flag[j]) cnt++;
            else continue;
            if(k>dp[n-i+1][cnt][0]+dp[n-i+1][cnt][1]){
                k-=dp[n-i+1][cnt][0]+dp[n-i+1][cnt][1];
            }
            else{
                flag[j]=1;
                ans[i]=j;
                break;
            }   
        }
    }
    for(int i=1;i<=n;i++)   if(!ans[i]){cout<<-1<<'\n';return; }
    for(int i=1;i<=n;i++)   cout<<ans[i]<<' ';
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int _ = 1;
    //cin >> _;
    while(_--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3704kb

input:

3 2

output:

2 1 3 

result:

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

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3584kb

input:

3 1

output:

1 2 3 

result:

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