QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#925416#2888. 棋盘2317663977WA 1ms4096kbC++234.5kb2025-03-04 16:14:372025-03-04 16:14:39

Judging History

This is the latest submission verdict.

  • [2025-03-04 16:14:39]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4096kb
  • [2025-03-04 16:14:37]
  • 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][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;
}

Details

Tip: Click on the bar to expand more detailed information

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: -100
Wrong Answer
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
01010101010101010101101010101010101010101010101010
10101010101010101010010101010101010101010101010101
01010101010101010101101010101010101010101010101010
10101010101010101010010101010101010101010101010101
01010101010101010101101010101010101010101...

result:

wrong answer There're two adjacent chesses.