QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#385110#5438. Half Mixedwsc2008WA 0ms3816kbC++141.7kb2024-04-10 15:36:412024-04-10 15:36:41

Judging History

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

  • [2024-04-10 15:36:41]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3816kb
  • [2024-04-10 15:36:41]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=1e6+9;
ll T,n,m;
ll chk(ll s,ll sum,ll i){
	if(s<i||sum<i*(i+1)/2)return 0;
	s-=i,sum-=i*(i+1)/2;
	ll mn=s,mx=s*(s+1)/2;
	if(mn<=sum&&sum<=mx)return 1;
	return 0;
}
void solve(){
	n=read(),m=read();
	ll l1=n*(n+1)/2,l2=m*(m+1)/2;
	if((l1&1)&&(l2&1))return puts("NO"),void();
	ll fl=0;
	if(l2&1)fl=1,swap(n,m),swap(l1,l2);
	//构造一个长度为 n 的 01 序列,使得全 0 或全 1 子序列恰好占一半
	//l_1, l_2, ..., l_k
	//(l_1 + 1) * l_1 / 2 + (l_2 + 1) * l_2 / 2 + ... = n*(n+1)/4
	ll sum=m*(m+1)/4,s=m;
	vector<ll>len;
	per(i,m,1){
		while(chk(s,sum,i)){
			s-=i,sum-=i*(i+1)/2;
			len.push_back(i);
		}
	}
	puts("YES");
	vector<vector<ll>>ans;
	ans.resize(n+2);
	rep(i,0,n)ans[i].resize(m+2);
	rep(i,1,n){
		ll cur=0,now=0;
		for(ll x:len){
			rep(j,1,x)now++,ans[i][now]=cur;
			cur^=1;
		}
	}
	if(!fl){
		rep(i,1,n){
			rep(j,1,m)write(ans[i][j]),putchar(' ');
			putchar('\n');
		}
	}
	else {
		rep(i,1,m){
			rep(j,1,n)write(ans[j][i]),putchar(' ');
			putchar('\n');
		}
	}
} 
bool Med;
int main(){
	cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
	T=read();
	while(T--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
2 3
1 1

output:

YES
0 1 0 
0 1 0 
NO

result:

wrong answer Token "YES" doesn't correspond to pattern "Yes|No" (test case 1)