QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302955#7778. Turning Permutationucup-team173#WA 1ms5868kbC++174.0kb2024-01-11 16:04:112024-01-11 16:04:12

Judging History

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

  • [2024-01-11 16:04:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5868kb
  • [2024-01-11 16:04:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) (int((x).size()))

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef pair<int, int> pii;

#define lll __int128_t
const int maxn=55;
int n;
lll k;
lll f[55][55][55][2];
const lll lim=2e18;
lll add(lll a,lll b){
    return min(a+b,lim);
}
lll mul(lll a,lll b){
    return min(lim,a*b);
}
void adto(lll&a,lll b){
    a=min(lim,a+b);
}
int q[maxn];
lll calc(){
    lll ans1=1,ans2=1;
    //ji xiang xia
    
    for(int i=1;i<n;i++){
        if(q[i]&&q[i+1]){
            if((i&1)&&q[i]<q[i+1]){
                ans1=0;break;
            }
            if(!(i&1)&&q[i]>q[i+1]){
                ans1=0;break;
            }
        }
    }
    for(int i=1,j;i<=n;i=j+1){
        j=i;
        if(q[i])continue;
        while(j+1<=n&&q[j+1]==0)j++;
        if(i==1){
            if(j%2==0){
                ans1=0;break;
            }
            ans1=mul(ans1,f[j][j][0][1]);
        }
        else if(j==n){
            if(i%2==0){
                ans1=0;break;
            }
            ans1=mul(ans1,f[j-i+1][j-i+1][0][n%2==0?0:1]);
        }
        else {
            if(i%2==0||j%2==0){
                ans1=0;break;
            }
            ans1=mul(ans1,f[j-i+1][j-i+1][0][1]);
        }
    }

    for(int i=1;i<n;i++){
        if(q[i]&&q[i+1]){
            if((i&1)&&q[i]>q[i+1]){
                ans2=0;break;
            }
            if(!(i&1)&&q[i]<q[i+1]){
                ans2=0;break;
            }
        }
    }
    
    for(int i=1,j;i<=n;i=j+1){
        j=i;
        if(q[i])continue;
        while(j+1<=n&&q[j+1]==0)j++;
        if(i==1){
            if(j%2==1){
                ans2=0;break;
            }
            ans2=mul(ans2,f[j][j][0][1]);
        }
        else if(j==n){
            if(i%2==1){
                ans2=0;break;
            }
            ans2=mul(ans2,f[j-i+1][j-i+1][0][n%2==0?1:0]);
        }
        else {
            if(i%2==1||j%2==1){
                ans2=0;break;
            }
            ans2=mul(ans2,f[j-i+1][j-i+1][0][1]);
        }
    }
    lll ans=add(ans1,ans2);
    int cnt=0;
    vector<int>v;
    for(int i=1,j;i<=n;i=j+1){
        j=i;
        if(q[i])continue;
        while(j+1<=n&&q[j+1]==0)j++;
        v.pb(j-i+1);
        cnt+=v.back();
    }
    vector<lll>vv;
    for(int i=1;i<=cnt;i++)vv.pb(i);
    for(lll i:v){
        for(int j=1;j<=i;j++){
            for(lll&o:vv){
                if(o%j==0){
                    o/=j;break;
                }
            }
        }
    }
    for(lll o:vv)ans=mul(ans,o);
    return ans;
}
void solve() {
    ll kll;
    cin>>n>>kll;
    kll--;
    k=kll;
    for(int len=1;len<=n;len++){
        for(int j=0;j<len;j++){
            f[len][1][j][0]=f[len][1][j][1]=1;
        }
        for(int i=1;i<=len;i++){
            for(int j=0;j<=len;j++){
                for(int w=0;w<j;w++){
                    adto(f[len][i+1][w][0],f[len][i][j][1]);
                }
                for(int w=j;w<len-i;w++){
                    adto(f[len][i+1][w][1],f[len][i][j][0]);
                }
            }
        }
    }
    // cout<<(ll)add(f[n][n][0][0],f[n][n][0][1])<<"asdaf\n";
    if(add(f[n][n][0][0],f[n][n][0][1])<k+1){
        cout<<"-1";return;
    }
    vector<pair<int,int> >cur;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(q[j])continue;
            q[j]=i;
            lll tmp=calc();
            if(k>=tmp)k-=tmp,q[j]=0;
            else break;
        }
    }
    vector<int>p(n+1);
    for(int i=1;i<=n;i++){
        p[q[i]]=i;
    }
    if(k!=0)cout<<"-1\n";
    else
    for(int i=1;i<=n;i++){
        cout<<p[i]<<" \n"[i==n];
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2

output:

2 1 3

result:

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

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

3 1

output:

1 3 2

result:

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

Test #6:

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

input:

3 10

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

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

input:

3 52

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

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

input:

3 756

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

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

input:

3 7721

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

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

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

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

input:

5 85

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

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

input:

5 846

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

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

input:

5 6957

output:

-1

result:

ok 1 number(s): "-1"

Test #15:

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

input:

8 1

output:

1 3 2 5 4 7 6 8

result:

ok 8 numbers

Test #16:

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

input:

8 7

output:

1 3 2 5 7 8 4 6

result:

ok 8 numbers

Test #17:

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

input:

8 71

output:

1 3 7 5 4 2 6 8

result:

ok 8 numbers

Test #18:

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

input:

8 863

output:

3 5 7 1 4 2 8 6

result:

ok 8 numbers

Test #19:

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

input:

8 7099

output:

-1

result:

ok 1 number(s): "-1"

Test #20:

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

input:

10 100000

output:

5 9 3 7 1 10 8 6 2 4

result:

wrong answer 1st numbers differ - expected: '10', found: '5'