QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#280769#7778. Turning Permutationucup-team135#WA 0ms3612kbC++203.7kb2023-12-09 17:53:242023-12-09 17:53:25

Judging History

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

  • [2023-12-09 17:53:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3612kb
  • [2023-12-09 17:53:24]
  • 提交

answer

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define app push_back
__int128 one=1;
__int128 ways[55][3];
__int128 c[55][55];
const int inf=2e18;
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    for(int i=0;i<55;++i)
    {
        for(int j=0;j<=i;++j)
        {
            if(i==0 || i==j) c[i][j]=1;
            else c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }
    ways[0][0]=1;ways[0][1]=1;ways[0][2]=1;
    for(int i=1;i<55;++i)
    {
        for(int l=0;l<i;++l)
        {
            ways[i][0]+=min(ways[l][1]*one*ways[i-l-1][1],one*inf)*one*c[i-1][l];
            ways[i][0]=min(ways[i][0],one*inf);
            if(l!=0 || (i==1)) ways[i][1]+=min(ways[l][2]*one*ways[i-l-1][1],one*inf)*c[i-1][l];
            ways[i][1]=min(ways[i][1],one*inf);
            if((l!=0 && (i-l-1)!=0) || (i==1)) ways[i][2]+=min(ways[l][2]*one*ways[i-l-1][2],one*inf)*c[i-1][l];
            ways[i][2]=min(ways[i][2],one*inf);
        }
    }
    /*vector<int> v(10);iota(v.begin(),v.end(),0LL);
    int answ=0;
    do {
        bool ok=1;
        for(int i=0;i<v.size()-2;++i)
        {
            if(v[i]>v[i+1] && v[i+1]>v[i+2]) ok=0;
            if(v[i]<v[i+1] && v[i+1]<v[i+2]) ok=0;
        }
        answ+=ok;
    }while(next_permutation(v.begin(),v.end()));
    cout<<answ<<" answ "<<endl;
    for(int i=1;i<55;++i)
    {
        for(int j=0;j<3;++j)
        {
            cout<<i<<" i "<<j<<" j "<<(int) (ways[i][j])<<" ways "<<endl;
        }
    }*/
    int n,k;cin>>n>>k;
    auto go2=[&](vector<pair<int,int> > zxc1)->int
    {
        vector<int> zxc;for(auto [l,r]:zxc1) zxc.app(r-l);
        int s= accumulate(all(zxc),0LL);
        __int128 res=1;
        for(int i:zxc)
        {
            res*=c[s][i];res=min(res,one*inf);s-=i;
        }
        return res;
    };
    auto go=[&](vector<int> a)->int
    {
        vector<int> b(n);fill(all(b),n);
        for(int i=0;i<n;++i)
        {
            if(a[i]!=(-1)) b[a[i]]=i;
        }
        for(int i=0;i<n-2;++i)
        {
            if(b[i]>b[i+1] && b[i+1]>b[i+2]) return 0;
            if(b[i]<b[i+1] && b[i+1]<b[i+2]) return 0;
        }
        int le=(-1);
        vector<pair<int,int> > zxc;
        for(int i=0;i<n;++i)
        {
            if(b[i]!=n)
            {
                if(le!=(-1))
                {
                    zxc.app({le,i});
                }
                le=(-1);continue;
            }
            else
            {
                if(le==(-1))
                {
                    le=i;
                }
            }
        }
        if(le!=(-1)) zxc.app({le,n});
        __int128 res=1;
        for(auto [l,r]:zxc)
        {
            int cnt=2-(l==0)-(r==n);
            res*=ways[r-l][cnt];res=min(res,one*inf);
        }
        res*=go2(zxc);res=min(res,one*inf);
        return res;
    };
    vector<int> a(n);fill(all(a),-1);
    //cout<<go(a)<<" go "<<endl;
    if(go(a)>k)
    {
        cout<<(-1);return 0;
    }
    int cf=0;
    bool ok=0;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(!count(a.begin(),a.end(),j))
            {
                a[i]=j;
                int cf1=cf+go(a);
                if(cf1>=k)
                {
                    ok=1;
                    break;
                }
                else
                {
                    cf=cf1;
                }
            }
        }
        if(!ok) break;
    }
    if(ok)
    {
        for(int x:a) cout<<x+1<<' ';
    }
    else
    {
        cout<<(-1);
    }
    return 0;
}

詳細信息

Test #1:

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

input:

3 2

output:

-1

result:

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