QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721664 | #7778. Turning Permutation | louhao088 | WA | 0ms | 3956kb | C++23 | 2.3kb | 2024-11-07 16:33:37 | 2024-11-07 16:33:38 |
Judging History
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'