QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#614648 | #5438. Half Mixed | mhw# | TL | 0ms | 11492kb | C++20 | 2.7kb | 2024-10-05 16:44:09 | 2024-10-05 16:44:12 |
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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11492kb
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 0 0 1 1 1 0 0 0 Yes 0 0 0 0 1 1 0 0 No No No Yes 0 0 0 0 1 1 1 1 0 0 0 0 Yes 0 0 0 0 0 0 1 1 1 0 0 0 No No Yes 0 0 0 0 1 1 0 No Yes 0 0 0 0 0 1 1 1 1 1...