QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#925420#2888. 棋盘2317663977WA 1ms4096kbC++234.5kb2025-03-04 16:18:362025-03-04 16:18:36

Judging History

This is the latest submission verdict.

  • [2025-03-04 16:18:36]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4096kb
  • [2025-03-04 16:18:36]
  • Submitted

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.