QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#620885#5438. Half MixedMENDAXWA 1ms3700kbC++142.0kb2024-10-07 22:04:562024-10-07 22:04:57

Judging History

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

  • [2024-10-07 22:04:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3700kb
  • [2024-10-07 22:04:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e6+10,mod=998244353;

int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef pair<int,int> PII;
int path[N];
vector<int> num; 

int ge(int it){
	return it*(it+1)/2;
}

bool dfs(int u,int n1,int n2,int op,int it){
	if(n2==u*(u+1)/4&&n1==u){
		return true;
	}
	if(it<=0)return false;
	int sheng=u*(u+1)/4-n2;
	int zz=it; 
	if(it>5){
		it=upper_bound(num.begin(),num.end(),sheng)-num.begin();
		it--;
		it=min(it,zz);	
	}
//	cout<<it<<endl;
	if(it==0) return false;
	int no=min((u-n1)/it,sheng/ge(it));
	if((u-n1)*ge(it)<sheng) return false;
//	if((u-n1)>sheng) return false;
	if((u-n1)==sheng){
		it=1;
	}
	for(int j=no;j>=0;j--){
		if(dfs(u,n1+j*it,n2+ge(it)*j,(op+j)%2,it-1)){ 
			int nums=0;
			for(int p=n1+1;p<=n1+it*j;p++){
				 path[p]=op;
				 nums++;
				 if(nums%it==0) op=1-op;
			}
			return true;
		}
		if(it==1) return false;
	} 
	return false;
}

void slove(){
	int n,m;cin>>n>>m;
	vector<vector<int>>g(n+4,vector<int>(m+5,0));
	if(n<m){
		if(n%4==0|n%4==3){
			dfs(n,0,0,0,n);
			for(int i=1;i<=m;i++){
				for(int j=1;j<=n;j++) g[j][i]=path[j];
			}
		}
		else if(m%4==3||m%4==0){
			dfs(m,0,0,0,m);
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++) g[i][j]=path[j];
			}
		}
		else {
			cout<<"No"<<endl;
			return ;
		}
	}
	else{
		if(m%4==3||m%4==0){
			dfs(m,0,0,0,m);
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++) g[i][j]=path[j];
			}
		}
		else if(n%4==0|n%4==3){
			dfs(n,0,0,0,n);
			for(int i=1;i<=m;i++){
				for(int j=1;j<=n;j++) g[j][i]=path[j];
			}
		}
		else {
			cout<<"No"<<endl;
			return ;
		}	
	}
	cout<<"Yes"<<endl;
	for(int i=1;i<=n;i++){	
		for(int j=1;j<=m;j++){
		 	cout<<g[i][j]<<" ";
		}
		cout<<endl;
	}
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	for(int i=0;i<=1e4;i++) num.push_back(i*(i+1)/2);
	int T=1;
	cin>>T;
	while(T--) slove();
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3700kb

input:

2
2 3
1 1

output:

Yes
0 0 0 
0 0 0 
No

result:

wrong answer 0 Mixed Submatrices Found, but 9 Expected (test case 1)