QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#771220#7778. Turning PermutationjiangzhihuiWA 0ms3888kbC++141.8kb2024-11-22 10:53:592024-11-22 10:53:59

Judging History

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

  • [2024-11-22 10:53:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3888kb
  • [2024-11-22 10:53:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55;
ll dp[N][N][N][2],k;
int n;
ll g[N][N];
vector<int> val;
vector<int> getans(int len){
    if(len==1){
        return vector<int>(1,val[0]);
    }
    for(int i=1;i<=len;i++){
        if(g[len][i]>=k){
            vector<int> t;
            t.push_back(val[i-1]);
            val.erase(val.begin()+i-1);
            vector<int> tmp=getans(len-1);
            for(auto v:tmp){
                t.push_back(v);
            }
            return t;
        }else{
            k-=g[len][i];
        }
    }
    return vector<int>();
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    dp[2][1][1][1]=1;
    dp[2][2][2][0]=1;
    for(int i=2;i<n;i++){
        for(int j=1;j<=i;j++){
            for(int k=1;k<=i;k++){
                if(j==1&&k!=1)continue;
                //1 before 2
                for(int p=1;p<=k;p++){
                    if(p==1){
                        dp[i+1][1][1][1]+=dp[i][j][k][0];
                    }else{
                        dp[i+1][j+1][p][1]+=dp[i][j][k][0];
                    }
                }
                //1 after 2
                for(int p=k;p<=i;p++){
                    dp[i+1][j+1][p+1][0]+=dp[i][j][k][1];
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            for(int k=1;k<=i;k++){
                g[i][j]+=dp[i][j][k][0]+dp[i][j][k][1];
            }
        }
    }
    ll s=0;
    for(int i=1;i<=n;i++){
        val.push_back(i);
        s+=g[n][i];
    }
    if(s<k){
        cout<<-1<<endl;
        return 0;
    }
    vector<int> ans=getans(n);
    for(auto v:ans){
        cout<<v<<" ";
    }
    cout<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

3 1

output:

1 2 3 

result:

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