QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325320#7780. Dark LaTeX vs. Light LaTeXZhouShang#WA 0ms3624kbC++201.4kb2024-02-11 07:58:452024-02-11 07:58:46

Judging History

This is the latest submission verdict.

  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2024-02-11 07:58:46]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3624kb
  • [2024-02-11 07:58:45]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
long long inf=1000000000000000001;
long long c[55][55];
long long dp[55];
int pos[55],a[55];
int main(){
	int n;
	long long k;
	cin>>n>>k;
	dp[1]=1;
	c[0][0]=c[1][0]=c[1][1]=1;
	for(int i=2;i<=n;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++) c[i][j]=min(inf,c[i-1][j-1]+c[i-1][j]);
	}
	dp[0]=dp[1]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			long long val=1;
			val*=(dp[j-1]+1)/2;
			if(inf/val<(dp[i-j]+1)/2) val=inf;
			else val*=(dp[i-j]+1)/2;
			if(inf/val<c[i-1][j-1]) val=inf;
			else val*=c[i-1][j-1];
			dp[i]+=val;
			if(dp[i]>inf) dp[i]=inf;
		}
	}
	if(k>dp[n]){
		puts("-1");
		return 0;
	}
	long long rest=k;
	for(int i=1,p1=-1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(pos[j]==0){
				if(i!=1&&(j-p1)%2&&(j+1<=n&&pos[j+1]==0||j-1>0&&pos[j-1]==0)) continue;
				long long val=1;
				int av=n-i;
				for(int l=1,cnt=0;l<=n+1;l++){
					if(l==n+1||pos[l]){
						if(cnt){
							if(inf/val<(dp[cnt]+1)/2) val=inf;
							else val*=(dp[cnt]+1)/2;
							if(inf/val<c[av][cnt]) val=inf;
							else val*=c[av][cnt];
						}
						av-=cnt,cnt=0;
					}
					else cnt++;
				} 
				cout<<i<<" "<<j<<" "<<val<<endl;
				if(val<rest) rest-=val;
				else{
					pos[j]=i;
					if(i==1) p1=j;
					break;
				}
			}
		}
	}
	for(int i=1;i<=n;i++) a[pos[i]]=i;
	for(int i=1;i<=n;i++) printf("%d%c",a[i],i==n?'\n':' ');
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

abab
ab

output:

-1

result:

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