QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#431545 | #6644. Red Black Grid | ucup-team3215# | RE | 0ms | 3732kb | C++23 | 2.1kb | 2024-06-05 18:19:13 | 2024-06-05 18:19:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pii = array<int, 2>;
int n;
vector<string> gr;
int check(int x, int y, int bad) {
return 0 <= x && x < n && 0 <= y && y < n ? (gr[x][y] == 'B' ? 1 : bad) : 0;
}
vector<int> dx = {-1, 1, 0, 0};
vector<int> dy = {0, 0, -1, 1};
int count(int x, int y, int bad) {
int res = 0;
for (int k = 0; k < 4; ++k) {
res += check(x + dx[k], y + dy[k], bad);
}
return res;
}
void solve() {
int k;
cin >> n >> k;
if (k == 1 || k + 1 == 2 * n * (n - 1)) {
cout << "Impossible\n";
return;
}
gr.assign(n, string(n, 'B'));
vector<vector<pii> > st(5);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
st[count(i, j, -1)].push_back({i, j});
}
}
int rk = 0;
while (rk < k) {
int delta = min(k - rk, 4);
int d = -1;
for (int i = 4; i > 0; --i) {
if (st[i].empty()) {
continue;
}
if ((d == -1 && rk + i + 1 < k) || rk + i == k) {
d = i;
}
}
assert(d != -1);
auto [x, y] = st[d].back();
st[d].pop_back();
int c = count(x, y, -1);
if (c != d) {
if (c > 0) {
st[c].push_back({x, y});
}
continue;
}
rk += d;
gr[x][y] = 'R';
}
if (rk == k) {
cout << "Possible\n";
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (gr[i][j] == 'R') ans += count(i, j, 0);
}
}
for (string & el : gr) {
cout << el << '\n';
}
if (ans != k) {
cout << n << ' ' << k << endl;
assert(ans == k);
}
return;
}
cout << n << ' ' << k << endl;
assert(false);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
input:
2 3 6 3 1
output:
Possible BBB BRB BBR Impossible
result:
ok correct! (2 test cases)
Test #2:
score: -100
Runtime Error
input:
4424 1 0 2 4 2 3 2 2 2 1 2 0 3 12 3 11 3 10 3 9 3 8 3 7 3 6 3 5 3 4 3 3 3 2 3 1 3 0 4 24 4 23 4 22 4 21 4 20 4 19 4 18 4 17 4 16 4 15 4 14 4 13 4 12 4 11 4 10 4 9 4 8 4 7 4 6 4 5 4 4 4 3 4 2 4 1 4 0 5 40 5 39 5 38 5 37 5 36 5 35 5 34 5 33 5 32 5 31 5 30 5 29 5 28 5 27 5 26 5 25 5 24 5 23 5 22 5 21 5...