QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#925420 | #2888. 棋盘 | 2317663977 | WA | 1ms | 4096kb | C++23 | 4.5kb | 2025-03-04 16:18:36 | 2025-03-04 16:18:36 |
Judging History
answer
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>
#include <iomanip>
using ll = long long;
const int N = 310;
int n, m;
int a[N];
int b[N];
vector<int> mm;
int ans[N][N];
void solve()
{
cin >> n >> m;
bool flag = false;
for (int i = 1;i <= m;i++)
{
cin >> a[i];
b[i] = a[i];
if (a[i] > (n + 1) / 2) flag = true;
else if (a[i] == (n + 1) / 2)
{
if (n % 2 == 1 && !mm.empty() && mm.back() == i - 1) flag = true;
else mm.push_back(i);
}
}
if (flag) // 某一列棋子过多或在奇数行情况下出现了相邻两列棋子都放满的情况
{
cout << "No\n";
return;
}
if (n % 2 == 0 || mm.empty()) // 偶数行或无棋子放满的情况
{
cout << "Yes\n";
for (int j = 1;j <= m;j++)
for (int i = 1;i <= n;i++)
{
if (b[j] && (i + j) % 2 == 0)
{
ans[i][j] = 1;
b[j]--;
}
else if (b[j] == 0) break;
}
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
cout << ans[i][j];
cout << '\n';
}
return;
}
for (auto j : mm) // 将需要放满的列先放上棋子
for (int i = 1;i <= n;i += 2)
ans[i][j] = 1;
for (int p = 1;p < mm.size();p++)
{
int pre = mm[p - 1] + 1, suf = mm[p] - 1;
if ((mm[p] - mm[p - 1]) % 2 == 1) // 中间有偶数列,在中间列中尽量寻找一个可以不用交替的地方1
{
bool flag = false; // 判断是否能找到一个不用交替的地方
for (int i = 2;i <= n;i += 2)
{
if (b[pre])
{
ans[i][pre] = 1;
b[pre]--;
}
else break;
}
for (int j = 1;j <= suf - pre;j++)
{
if (!flag) // 暂未找到可不交替的列
{
if (j % 2 == 1) // 上一列放置在偶数行
{
if (a[pre + j] + a[pre + j - 1] <= n / 2) // 不用交替
{
flag = true;
for (int i = 1;i <= n;i++)
{
if ((i + j) % 2 == 1 && ans[i][pre + j - 1] != 1 && b[pre + j])
{
ans[i][pre + j] = 1;
b[pre + j]--;
}
else if (b[pre + j] == 0) break;
}
}
else // 需要交替
{
for (int i = 1;i <= n;i++)
{
if ((i + j) % 2 == 0 && b[pre + j])
{
ans[i][pre + j] = 1;
b[pre + j]--;
}
else if (b[pre + j] == 0) break;
}
}
}
else // 上一列放置在奇数行
{
if (a[pre + j] + a[pre + j - 1] <= n / 2 + 1) // 不用交替
{
flag = true;
for (int i = 1;i <= n;i++)
{
if ((i + j) % 2 == 1 && ans[i][j - 1] != 1 && b[pre + j])
{
ans[i][pre + j] = 1;
b[pre + j]--;
}
else if (b[pre + j] == 0) break;
}
}
else // 需要交替
{
for (int i = 1;i <= n;i++)
{
if ((i + j) % 2 == 0 && b[pre + j])
{
ans[i][pre + j] = 1;
b[pre + j]--;
}
else if (b[pre + j] == 0) break;
}
}
}
}
else // 已找到可交替的列
{
for (int i = 1;i <= n;i++)
{
if ((i + j) % 2 == 1 && b[pre + j])
{
ans[i][pre + j] = 1;
b[pre + j]--;
}
else if (b[pre + j] == 0) break;
}
}
}
if (!flag) // 未找到满足条件的位置,无解
{
cout << "No\n";
return;
}
}
else // 中间有奇数列,直接交替放置
{
for (int j = 0;j <= suf - pre;j++)
{
for (int i = 1;i <= n;i++)
{
if ((i + j) % 2 == 0 && b[pre + j])
{
ans[i][pre + j] = 1;
b[pre + j]--;
}
else if (b[pre + j] == 0) break;
}
}
}
}
int pre = mm.front() - 1, suf = mm.back() + 1;
//cout << pre << ' ' << suf << '\n';
//cout << b[4] << '\n';
for (int j = 0;pre - j > 0;j++)
{
for (int i = 1;i <= n;i++)
if ((i + j) % 2 == 0 && b[pre - j])
{
ans[i][pre - j] = 1;
b[pre - j]--;
}
else if (b[pre - j] == 0) break;
}
for (int j = 0;suf + j <= m;j++)
{
for (int i = 1;i <= n;i++)
if ((i + j) % 2 == 0 && b[suf + j])
{
ans[i][suf + j] = 1;
b[suf + j]--;
}
else if (b[suf + j] == 0) break;
}
cout << "Yes\n";
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
cout << ans[i][j];
cout << '\n';
}
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
3 4 2 1 2 1
output:
Yes 1010 0101 1010
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
299 50 150 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 150 123 26 150 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 150
output:
Yes 10101010101010101010010101010101010101010101010101 01010101010101010101001010101010101010101010101010 10101010101010101010010101010101010101010101010101 01010101010101010101001010101010101010101010101010 10101010101010101010010101010101010101010101010101 01010101010101010101001010101010101010101...
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1 300 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 ...
output:
Yes 00100010101000100001000100101010000000100001010000100100010010101000101010100010101000000000010010101010100010101001010010010010100001000100100101010001010100010000101010001010100101010010100100010100100100101010010100010010100010101010101010010010010010101010010010010010010001010101010101001010...
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3968kb
input:
239 300 119 120 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 ...
output:
No
result:
wrong answer Incorrect Yes/No.