QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#771327#7778. Turning PermutationjiangzhihuiWA 0ms5712kbC++142.1kb2024-11-22 11:45:212024-11-22 11:45:22

Judging History

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

  • [2024-11-22 11:45:22]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5712kb
  • [2024-11-22 11:45:21]
  • 提交

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;
map<int,bool> vis;
bool cmp(int x,int y){
    if(y==x+1&&vis[x-1])return false;
    if(x==y+1&&vis[y-1])return true;
    if(y==x-1&&vis[x+1])return false;
    if(y==x+1&&vis[y+1])return true;
    return x<y;
}
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]);
            vis[val[i-1]]=true;
            val.erase(val.begin()+i-1);
            sort(val.begin(),val.end(),cmp);
            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: 3524kb

input:

3 2

output:

2 1 3 

result:

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

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

3 1

output:

1 3 2 

result:

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

Test #6:

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

input:

3 10

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

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

input:

3 52

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

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

input:

3 756

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

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

input:

3 7721

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

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

input:

5 1

output:

1 3 2 5 4 

result:

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

Test #11:

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

input:

5 8

output:

2 4 1 3 5 

result:

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

Test #12:

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

input:

5 85

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

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

input:

5 846

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

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

input:

5 6957

output:

-1

result:

ok 1 number(s): "-1"

Test #15:

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

input:

8 1

output:

1 3 2 5 4 7 6 8 

result:

ok 8 numbers

Test #16:

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

input:

8 7

output:

1 3 2 4 6 8 5 7 

result:

wrong answer 4th numbers differ - expected: '5', found: '4'