QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#601333#7778. Turning PermutationargtargWA 0ms3484kbC++204.0kb2024-09-29 22:24:092024-09-29 22:24:10

Judging History

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

  • [2024-09-29 22:24:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3484kb
  • [2024-09-29 22:24:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define ll long long
#define endl '\n'
#define pii pair<int, int>
void solve();
void init();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    init();
    while (T--) {
        solve();
    }
    return 0;
}

const int N = 51;
int C[N][N];
void init() {
    for(int i=0;i<N;i++) {
        C[i][0]=1;
    }
    // int mi=0;
    for(int i=1;i<N;i++) {
        for(int j=1;j<=i;j++) {
            C[i][j]=C[i-1][j-1]+C[i-1][j];
            // cout<<C[i][j]<<' ';
            // mi=min(mi,C[i][j]);
        }
        // cout<<endl;
    }
    // cout<<mi<<endl;
}

void solve() {
    ll ni,numi;
    cin>>ni>>numi;
    int n,num;
    // cin>>n>>num;
    n=ni;
    num=numi;
    vector<int>p(n+2);
    p[n+1]=n+1;
    vector<vector<int>>dp(n+1,vector<int>(n+1));
    vector<int>sum1(n+1);
    sum1[1]=sum1[0]=1;
    sum1[2]=2;
    int ttt=1;
    for(int i=3;i<=n;i++) {
        for(int j=1;j<=i;j++) {
            int l=j-1,r=i-j;
            dp[i][j]=C[l+r][l]*max(ttt,sum1[l]/2)*max(ttt,sum1[r]/2);
            sum1[i]+=dp[i][j];
            // if(i==3)cout<<dp[i][j]<<' ';
        }
    }
    // cout<<sum1[3]<<endl;
    for(int i=1;i<=n;i++) {
        int ok=0;
        for(int j=1;j<=n;j++) {
            if(p[j]!=0)continue;
            int ook=1;
            p[j]=i;
            for(int k=max(j-2,ttt);k<=j;k++) {
                if(k+2>n)continue;
                int ok=0;
                for(int q=k;q<=k+2;q++) {
                    if(p[q]==0)ok=1;
                }
                if(ok==1)continue;
                if(p[k]<p[k+1]&&p[k+1]<p[k+2]||p[k]>p[k+1]&&p[k+1]>p[k+2]) {
                    ook=0;
                }

            }
            for(int k=1;k<=n;k++) {
                if(p[k]==0) {
                    if(k>=3) {
                        if(p[k-2]!=0&&p[k-1]!=0&&p[k-1]>p[k-2])ook=0;
                    }
                    if(k+2<=n) {
                        if(p[k+2]!=0&&p[k+1]!=0&&p[k+1]>p[k+2])ook=0;
                    }
                }
            }
            p[j]=0;
            if(ook==0)continue;
            /*if(i==3) {
                cout<<"this"<<endl;
            }*/
            p[j]=i;
            int l=0;
            int tmp=1;
            int okk=1;
            int sum=n-i;
            for(int k=1;k<=n+1;k++) {
                if(p[k]!=0) {
                    if(!(l==0||k==n+1)) {
                        if(k-1-l!=0&&(k-1-l)&1^1) {
                            ok=0;
                            tmp=0;
                            break;
                        }
                    }
                    int c=C[sum][k-l-1]*max(ttt,sum1[k-l-1]/2);
                    // if(i*j==1)cout<<"c== "<<c<<endl;
                    if((num+c-1)/c<=tmp||ok==1||C[sum][k-l-1]*tmp>=num||tmp*(sum1[k-l-1]/2)>=num
                        ||C[sum][k-l-1]>=tmp||C[sum][k-l-1]<0||C[sum][k-l-1]*tmp<0||
                        (sum1[k-l-1]/2)<0||(sum1[k-l-1]/2)*tmp<0||(sum1[k-l-1]/2)>=num) {
                        ok=1;
                    }
                    else {
                        tmp*=c;
                        // if(i==4&&j==5)cout<<(ll)C[sum][k-l-1]<<' '<<(ll)sum1[k-l-1]/2<<endl;?
                        sum-=(k-1-l);
                    }
                    l=k;
                }
            }
            // cout<<"i== "<<(ll)i;
            // cout<<" j== "<<(ll)j;
            // cout<<" ok== "<<(ll)ok<<endl;
            if(ok==1)break;
            p[j]=0;
            num-=tmp;

            // cout<<" tmp== "<<(ll)tmp<<endl;
        }
        if(ok==0) {
             // cout<<"-1 "<<i<<endl;
            cout<<-1<<endl;
            return;
        }
    }
    vector<int>pos(n+1);
    for(int i=1;i<=n;i++) {
        pos[p[i]]=i;
    }
    for(int i=1;i<=n;i++) {
        cout<<(ll)pos[i]<<' ';
    }
    cout<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3484kb

input:

3 2

output:

1 3 2 

result:

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