QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#385110 | #5438. Half Mixed | wsc2008 | WA | 0ms | 3816kb | C++14 | 1.7kb | 2024-04-10 15:36:41 | 2024-04-10 15:36:41 |
Judging History
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)