QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#620662#5438. Half MixedMENDAXML 0ms0kbC++141.8kb2024-10-07 20:08:052024-10-07 20:08:06

Judging History

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

  • [2024-10-07 20:08:06]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-10-07 20:08:05]
  • 提交

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; 
	it=upper_bound(num.begin(),num.end(),sheng)-num.begin();
	it--;
	if(it==0) return false;
	for(int j=min((u-n1)/it,sheng/ge(it));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
Memory Limit Exceeded

input:

2
2 3
1 1

output:


result: