QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620443#5438. Half MixedDoubeecatTL 1ms3780kbC++201.7kb2024-10-07 18:10:462024-10-07 18:10:46

Judging History

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

  • [2024-10-07 18:10:46]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3780kb
  • [2024-10-07 18:10:46]
  • 提交

answer

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

int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef pair<int,int> PII;

vector<int> num;
int path[N];

bool dfs(int u,int n1,int n2,int op){
	if(n2==u*(u+1)/4&&n1==u){
		return true;
	}
	
	if(u*(u+1)/4-n2==u-n1){
		for(int p=n1+1;p<=u;p++) path[p]=op,op=1-op;
		return true;
	}
	
	int sheng=u*(u+1)/4-n2;
	auto it=upper_bound(num.begin(),num.end(),sheng)-num.begin();
	it--;
	
	for(int i=it;i>=1;i--){
		int st=1;
		if(i==1){ 
//			cout<<u<<" "<<n1<<" "<<n2<<endl;
			if(u*(u+1)/4-n2==u-n1){
				for(int p=n1+1;p<=u;p++) path[p]=op,op=1-op;
				return true;
			}
			else return false;
		}
		for(int j=st;j<=1000000000000;j++){
			if(i*j+n1>u) break;
			if(num[i]*j+n2>(u+1)*u/4) break;
			if(dfs(u,n1+j*i,n2+num[i]*j,(op+j)%2)){ 
				int num=0;
				for(int p=n1+1;p<=n1+i*j;p++){
					 path[p]=op;
					 num++;
					 if(num%i==0) op=1-op;
				}
				return true;
			}
		} 
	}
	return false;
}

void slove(){
	int n,m;cin>>n>>m;
	for(int i=0;i<=1e4;i++) num.push_back(i*(i+1)/2);
	
	vector<vector<int>>g(n+1,vector<int>(m+1,0));
	if(m%4==3||m%4==0){
		dfs(m,0,0,0);
		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);
		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);
	int T=1;
	cin>>T;
	while(T--) slove();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3780kb

input:

2
2 3
1 1

output:

Yes
0 1 0 
0 1 0 
No

result:

ok OK, Accepted. (2 test cases)

Test #2:

score: -100
Time Limit Exceeded

input:

5382
1 1
1 2
2 1
1 3
2 2
3 1
1 4
2 3
3 2
4 1
1 5
2 4
3 3
4 2
5 1
1 6
2 5
3 4
4 3
5 2
6 1
1 7
2 6
3 5
4 4
5 3
6 2
7 1
1 8
2 7
3 6
4 5
5 4
6 3
7 2
8 1
1 9
2 8
3 7
4 6
5 5
6 4
7 3
8 2
9 1
1 10
2 9
3 8
4 7
5 6
6 5
7 4
8 3
9 2
10 1
1 11
2 10
3 9
4 8
5 7
6 6
7 5
8 4
9 3
10 2
11 1
1 12
2 11
3 10
4 9
5 8
6 ...

output:

No
No
No
Yes
0 1 0 
No
Yes
0 
1 
0 
Yes
0 0 1 0 
Yes
0 1 0 
0 1 0 
Yes
0 0 
1 1 
0 0 
Yes
0 
0 
1 
0 
No
Yes
0 0 1 0 
0 0 1 0 
Yes
0 1 0 
0 1 0 
0 1 0 
Yes
0 0 
0 0 
1 1 
0 0 
No
No
No
Yes
0 0 1 0 
0 0 1 0 
0 0 1 0 
Yes
0 1 0 
0 1 0 
0 1 0 
0 1 0 
No
No
Yes
0 0 0 0 1 1 0 
No
Yes
0 0 0 0 0 
1 1 1 1 1...

result: