QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#614633 | #5438. Half Mixed | mhw# | WA | 0ms | 11492kb | C++20 | 2.7kb | 2024-10-05 16:43:11 | 2024-10-05 16:43:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
const int maxn = 100;
const int N = 1e6 + 7;
int f[51][200]{};
ll w[1000010];
int n, m;
int work(ll tot, int tp)
{
vector<int> ans;
ll W = (tot + 1) * tot / 4;
ll V = tot;
if (W < V){
puts("No");
return -1;
}
while (W && V)
{
if (W < maxn)
break;
int id = upper_bound(w + 1, w + 2000, min(W, W + 1 - V)) - w - 1; // 小于等于min(W, W + 1 - V)的
W -= w[id] + id;
V -= id;
ans.push_back(id);
}
// W 填充的 W < maxn && W >= V
// V 格子数
while (W != 0 && V != 0)
{
int t = f[V][W];
ll dt = t * (t + 1) / 2;
ans.push_back(t);
W -= dt, V -= t;
}
puts("YES");
if (tp == 1)
{
int now = 0;
for (auto x : ans)
{
for (int j = 1; j <= x; ++j)
{
for (int i = 1; i <= m; ++i)
cout << now << " ";
puts("");
}
now ^= 1;
}
return 1;
}
else
{
for (int i = 1; i <= n; i++)
{
int now = 0;
for (auto x : ans)
{
for (int j = 1; j <= x; ++j)
{
cout << now << " ";
}
now ^= 1;
}
puts("");
}
return 1;
}
}
void slv()
{
int op = -1;
cin >> n >> m;
if (n % 4 == 0 || n % 4 == 3){
op = n;
if(work(n, 1) == 1) return;
}
if (m % 4 == 0 || m % 4 == 3){
op = m;
if(work(m, 2) == 1) return;
}
if (op == -1)
{
puts("No");
return;
}
}
void init()
{
for (int i = 1; i <= 1000000; ++i)
w[i] = (i + 1) * i / 2 - i;
memset(f, -1, sizeof(f));
vector<int> g(51);
g[0] = 0;
for (int i = 1; i <= 50; i++)
{
g[i] = i * (i + 1) / 2;
}
f[0][0] = 0;
for (int i = 0; i <= 50; i++)
{
for (int j = 0; j < 101; j++)
{
if (f[i][j] == -1)
continue;
for (int k = 0; k <= 50; k++)
{
if (j + g[k] < 101 && i + k < 50)
{
f[i + k][j + g[k]] = max(f[i + k][j + g[k]], k);
}
}
}
}
}
signed main()
{
// ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
init();
int _;
cin >> _;
while (_--)
slv();
}
/*
2
2 3
1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 11492kb
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)