QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#122773 | #6644. Red Black Grid | wnmrmr# | RE | 1ms | 3396kb | C++23 | 2.4kb | 2023-07-11 03:08:52 | 2023-07-11 03:08:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) //cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#define pb push_back
// #define int long long
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, k;
void solve () {
cin >> n >> k;
int mx = 2 * (n - 1) * n;
if (k == 1 || k == mx - 1) {
cout << "Impossible\n";
return;
}
vector ans (n, vector<int> (n));
cout << "Possible\n";
if (k < n * (n - 1)) {
int i = 0;
while (k > n) {
for (int j = 0; j < n; j++) ans[i][j]++;
if (i) k -= n;
i += 2;
k -= n;
}
if (k > 0) {
for (int j = 0; j < k - 1; j++) ans[i][j]++;
}
}
else if (k >= n * (n - 1)) {
// se for maior que a metade
// vamos quadricular
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) ans[i][j] = (i + j) & 1;
vector<pair<int, int>> adj[5];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) if (!ans[i][j]) {
int vis = 0;
for (int p = 0; p < 4; p++) {
int ii = i + dx[p], jj = j + dy[p];
if (ii < 0 || ii >= n || jj < 0 || jj >= n) continue;
vis++;
}
// dbg (vis);
adj[vis].pb ({i, j});
}
auto paint = [&] (int id) {
auto [x, y] = adj[id].back (); adj[id].pop_back ();
ans[x][y] ^= 1;
};
if (k & 1) {
paint (3);
}
while (k > 6) {
if (adj[3].size () < 2) break;
paint (3);
paint (3);
k -= 6;
}
while (k > 2) {
if (adj[4].size () == 0) break;
paint (4);
k -= 4;
}
if (k == 2) paint (2);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (ans[i][j]) cout << 'R';
else cout << 'B';
}
cout << "\n";
}
}
signed main () {
ios::sync_with_stdio(0);cin.tie(0);
int t; cin >> t;
while (t--)
solve ();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3396kb
input:
2 3 6 3 1
output:
Possible BRB RRR BRR 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...