QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721664#7778. Turning Permutationlouhao088WA 0ms3956kbC++232.3kb2024-11-07 16:33:372024-11-07 16:33:38

Judging History

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

  • [2024-11-07 16:33:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3956kb
  • [2024-11-07 16:33:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define lowbit(i) (i&(-i))
#define fi first
#define se second
#define pi pair<int,int>
#define int long long
const int inf=1e18,maxn=105,M=100005;
inline int read(){
	char ch=getchar();int x=0;bool f=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
int n,k,T,x,y,res=0,a[maxn];
int C[maxn][maxn],f[maxn],g[maxn][maxn],ans[maxn];
bool solve(int x){
    int sum=1,s=0;
    double g=0,h=log(1e18);
    for(int i=1;i<=n;i++){
        if(!a[i])s++;
        else if(s){
            if(s%2==0&&s!=i-1)return 0;
            s=0;
        }
    }
    s=0;
    for(int i=1;i<=n;i++){
        if(!a[i])s++;
        else if(s){
            g=g+log(C[x][s])+log(f[s]);
            if(g>h)return 1;
            sum=sum*f[s]*C[x][s];
            x-=s;
            s=0;
        }
    }
    if(s){
        g=g+log(C[x][s])+log(f[s]);
        if(g>h)return 1;
        sum=sum*f[s]*C[x][s];
    }
    //cout<<sum<<" "<<x<<endl;
    if(sum>=k)return 1;
    else {
        k-=sum;
        return 0;
    }
}
signed main(){
	n=read(),k=read();C[0][0]=1;
    for(int i=1;i<=n;i++){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
            if(C[i][j]>inf)C[i][j]=inf;
            //cout<<C[i][j]<<" "<<i<<" "<<j<<endl;
        }
    }g[1][1]=1,f[1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(i&1){
                for(int k=1;k<j;k++){
                    g[i][j]+=g[i-1][k];
                    g[i][j]=min(g[i][j],inf);
                }
                
            }
            else {
                for(int k=j;k<i;k++){
                    g[i][j]+=g[i-1][k];
                    g[i][j]=min(g[i][j],inf);
                }
            }
            f[i]+=g[i][j];
            f[i]=min(f[i],inf);
        }//cout<<f[i]<<" ";
    }//scout<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(!a[j]){
                a[j]=i;
                if(solve(n-i))break;
                if(j==n){puts("-1");exit(0);}
                a[j]=0;
            }
        }
    }
    for(int i=1;i<=n;i++)ans[a[i]]=i;
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    
}

详细

Test #1:

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

input:

3 2

output:

2 1 3 

result:

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

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

3 1

output:

1 2 3 

result:

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