QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252330#7778. Turning PermutationLynkcat#WA 1ms3896kbC++203.8kb2023-11-15 18:24:472023-11-15 18:24:47

Judging History

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

  • [2023-11-15 18:24:47]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3896kb
  • [2023-11-15 18:24:47]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
const int inf=1e18,N=255;
int cc[N][N],ans[N],bl;
int n,m;
int f[N],h[N];
inline int mul(int x,int y)
{
    if (x==0||y==0) return 0;
    if (inf/y<x) return inf;
    return x*y;
}
inline int add(int x,int y)
{
    return min(inf,x+y);
}
inline int C(int x,int y)
{
    if (x<y||y<0) return 0;
    return cc[x][y];
}
struct node
{
    int l,r,v;
};
vector<node>g;
void dfs(int k)
{
    if (k>n)
    {
        if (m>1)
        {
            cout<<"-1\n";
            return;
        }
        for (int i=1;i<=n;i++) cout<<ans[i]<<" ";
        cout<<'\n';
        return;
    }
    for (auto U:g)
    {
        int l=U.l,r=U.r,v=U.v;
        for (int i=l;i<=r;i++)
            if ((i-l)%2==v||r-l+1==1)
            {
                int x=i-l;
                int y=r-i;
                int coef=1,tot=0;
                if (x) 
                {
                    coef=mul(coef,C(tot+x,tot)),tot+=x;
                    coef=mul(coef,h[x]);
                }
                if (y) 
                {
                    coef=mul(coef,C(tot+y,tot)),tot+=y;
                    coef=mul(coef,h[y]);
                }
                for (auto V:g)
                {
                    int L=V.l,R=V.r;
                    if (L!=l)
                    {
                        coef=mul(coef,C(tot+R-L+1,tot)),tot+=R-L+1;
                        coef=mul(coef,h[R-L+1]);
                    }
                }
                // cout<<"????"<<i<<" "<<m<<" "<<coef<<endl;
                if (coef<m)
                {
                    m-=coef;
                    continue;
                } else
                {
                    vector<node>nxt;
                    for (auto V:g)
                        if (V.l!=l) nxt.push_back(V);
                    if (x)
                    {
                        nxt.push_back((node){l,i-1,v});
                    }
                    if (y)
                    {
                        nxt.push_back((node){i+1,r,1});
                    }
                    nxt.swap(g);
                    ans[k]=i;
                    dfs(k+1);
                    return;
                }
            }
    }
    cout<<"-1\n";
    return;
}
void BellaKira()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        int coef=mul(C(i-1+n-i,i-1),mul(h[i-1],h[n-i]));
        // cout<<i<<" "<<m<<" "<<coef<<endl;
        if (m>coef)
        {
            m-=coef;
        } else
        {
            ans[1]=i;
            if (i-1)
                g.push_back((node){1,i-1,(i-1)%2});
            if (n-i)
                g.push_back((node){i+1,n,1});
            dfs(2);
            return;
        }
    }
    dfs(1);
}
signed main()
{
    cc[0][0]=1;
    for (int i=1;i<=200;i++)
    {
        cc[i][0]=1;
        for (int j=1;j<=i;j++)
        {
            cc[i][j]=cc[i-1][j-1]+cc[i-1][j];
            cc[i][j]=min(cc[i][j],inf);
        }
    }
    h[0]=1;
    f[1]=1;h[1]=1;
    for (int i=2;i<=200;i++)
    {
        f[i]=h[i-1];
        for (int j=1;j+1<i;j++)
            f[i]=add(f[i],mul(C(j,i-1-j),mul(f[j],h[i-1-j])));
        
        for (int j=1;j<i;j+=2)
            h[i]=add(h[i],mul(C(j,i-1-j),mul(h[j],h[i-1-j])));
    }
    // return 0;
    IOS;
    cin.tie(0);
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3748kb

input:

3 2

output:

2 1 3 

result:

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

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

3 1

output:

1 3 2 

result:

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

Test #6:

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

input:

3 10

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

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

input:

3 52

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

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

input:

3 756

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

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

input:

3 7721

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

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

input:

5 1

output:

1 3 2 5 4 

result:

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

Test #11:

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

input:

5 8

output:

3 1 2 5 4 

result:

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