社区讨论

How E?

学术版参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@miaclbs3
此快照首次捕获于
2025/11/22 21:51
3 个月前
此快照最后确认于
2025/11/22 22:32
3 个月前
查看原帖
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;

using i32 = int32_t;
using i64 = int64_t;
using ui32 = uint32_t;
using ui64 = uint64_t;

namespace strdp {
	const int N = 2e5;
	int n, m, r[N + 5], c[N + 5], cntr[N + 5], cntc[N + 5], idxr[N + 5], idxc[N + 5], rp[N + 5], cp[N + 5], qwq[N + 5];
	void main() {
		cin >> n >> m;
		for (int i = 0; i <= n * m; i++) cntr[i] = cntc[i] = qwq[i] = 0;
		for (int i = 1; i <= n; i++) rp[i] = 1;
		for (int i = 1; i <= m; i++) cp[i] = 1;
		int mxr = 0, mxc = 0;
		for (int i = 1; i <= n; i++) cin >> r[i], mxr = max(mxr, r[i]);
		for (int i = 1; i <= m; i++) cin >> c[i], mxc = max(mxc, c[i]);
		if (mxr != n * m || mxc != n * m) {
			cout << "No\n";
			return;
		}
		for (int i = 1; i <= n; i++) cntr[r[i]]++;
		for (int i = 1; i <= m; i++) cntc[c[i]]++;
		int rr = 0, cc = 0;
		for (int i = n * m; i >= 1; i--) {
			rr += cntr[i], cc += cntc[i];
			if (rr * cc < n * m - i + 1) {
				cout << "No\n";
				return;
			}
		}
		cout << "Yes\n";
		vector< vector<int> > res(n + 1, vector<int>(m + 1));
		for (int i = 1; i <= n; i++) idxr[i] = i;
		for (int i = 1; i <= m; i++) idxc[i] = i;
		sort(idxr + 1, idxr + n + 1, [&] (int x, int y) {
			return r[x] > r[y];
		});
		sort(idxc + 1, idxc + m + 1, [&] (int x, int y) {
			return c[x] > c[y];
		});
		int r2 = 1, c2 = 1;
		for (int i = n * m; i >= 1; i--) {
			bool tr = (r2 <= n && r[idxr[r2]] == i), tc = (c2 <= m && c[idxc[c2]] == i);
			if (tr && tc) {
				res[idxr[r2]][idxc[c2]] = i;
				qwq[i]++;
				rp[idxr[r2]] = max(rp[idxr[r2]], idxc[c2] + 1);
				cp[idxc[c2]] = max(cp[idxc[c2]], idxr[r2] + 1);
				r2++;
				c2++;
			} else if (tr) {
				int row = idxr[r2];
				int col = rp[row];
				while (col <= m && (c[col] < i || res[row][col] != 0)) col++;
				if (col <= m) {
					res[row][col] = i;
					qwq[i]++;
					rp[row] = col + 1;
					cp[col] = max(cp[col], row + 1);
				}
				r2++;
			} else if (tc) {
				int col = idxc[c2];
				int row = cp[col];
				while (row <= n && (r[row] < i || res[row][col] != 0)) row++;
				if (row <= n) {
					res[row][col] = i;
					qwq[i]++;
					cp[col] = row + 1;
					rp[row] = max(rp[row], col + 1);
				}
				c2++;
			}
		}
		int cnt = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (res[i][j]) continue;
				while (qwq[cnt]) cnt++;
				res[i][j] = cnt;
				cnt++;
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << res[i][j] << " ";
			}
			cout << "\n";
		}
	}
}

i32 main() {

	int t = 1;
	cin >> t;

	while (t--) strdp::main();
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...