社区讨论
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 条回复,欢迎继续交流。
正在加载回复...