QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#279780#7778. Turning Permutationucup-team2279#WA 0ms4036kbC++202.0kb2023-12-09 09:03:322023-12-09 09:03:33

Judging History

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

  • [2023-12-09 09:03:33]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4036kb
  • [2023-12-09 09:03:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mk make_pair
#define lowbit(x) (x&(-x))
#define pb emplace_back
#define pr pair<int,int>
#define let const auto
#define all(A) A.begin(),A.end()
void chkmin(int &x,int y){x=min(x,y);}
void chkmax(int &x,int y){x=max(x,y);}
const int N=55;
int read(){
	int x=0,f=1; char c=getchar();
	while(('0'>c||c>'9')&&c!='-') c=getchar();
	if(c=='-') f=0,c=getchar();
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?x:-x;
}
ll f[N][2][2],C[N][N];
int n; ll k; 
void mul(ll &t,ll p){
	t=min((__int128)k,(__int128)t*p);
}
ll calc(vector <pr> range,int i){
	auto get = [&](int l,int r){
		return f[r-l+1][l!=1][r!=n];
	};
	ll ans=1; int rn=-1;
	for(auto [l,r]:range) rn+=r-l+1;
	for(auto [l,r]:range){
		if(i>=l&&i<=r) mul(ans,get(l,i-1)),mul(ans,get(i+1,r)),mul(ans,C[rn][i-l]),mul(ans,C[rn-=i-l][r-i]),rn-=r-i;
		else mul(ans,get(l,r)),mul(ans,C[rn][r-l+1]);
	}
	return ans;
}
vector <pr> cancel(vector <pr> t,int i){
	vector <pr> s;
	for(auto [l,r]:t){
		if(i>=l&&i<=r){
			if(i>l) s.pb(l,i-1);
			if(i<r) s.pb(i+1,r);
		}
		else s.pb(l,r);
	}
	return s;
}
void print(vector <pr> range,ll res){
	vector <int> g(n+1,0);
	for(auto [l,r]:range){
		if(l==r) g[l]=1;
		for(int i=l+(l>1); i<=r-(r<n); i++) g[i]=1;
	} 
	for(int i=1; i<=n; i++) if(g[i]){
		ll val=calc(range,i);
		if(res<=val) return printf("%d ",i),print(cancel(range,i),res);
		res-=val;
	}
}
int main(){
	cin>>n>>k;
	for(int i:{0,1})
		for(int j:{0,1}) f[0][i][j]=f[1][i][j]=1;
	for(int i=0; i<=n; i++){
		C[i][0]=1;
		for(int j=1; j<=i; j++) C[i][j]=min(k,C[i-1][j-1]+C[i-1][j]);
	}
	for(int i=2; i<=n; i++){
		for(int j:{0,1})
			for(int p:{0,1}){
				for(int t=j+1; t<=i-p; t++)
					f[i][j][p]=min(k,f[i][j][p]+(ll)min((__int128)k,min((__int128)k,(__int128)f[t-1][j][1]*f[i-t][1][p])*C[i-1][t-1]));
			}
	}
	if(f[n][0][0]<k) return puts("-1"),0;
	vector <pr> s={{1,n}};
	print(s,k);
	return 0;
}

详细

Test #1:

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

input:

3 2

output:

2 1 3 

result:

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

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

3 1

output:

1 3 2 

result:

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

Test #6:

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

input:

3 10

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

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

input:

3 52

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

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

input:

3 756

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

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

input:

3 7721

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

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

input:

5 1

output:

1 3 2 5 4 

result:

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

Test #11:

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

input:

5 8

output:

2 4 1 3 5 

result:

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

Test #12:

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

input:

5 85

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

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

input:

5 846

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

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

input:

5 6957

output:

-1

result:

ok 1 number(s): "-1"

Test #15:

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

input:

8 1

output:

1 3 2 5 4 7 6 8 

result:

ok 8 numbers

Test #16:

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

input:

8 7

output:

1 3 2 5 7 6 4 8 

result:

wrong answer 6th numbers differ - expected: '8', found: '6'