QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#130021 | #6644. Red Black Grid | smosp# | WA | 23ms | 3496kb | C++20 | 2.9kb | 2023-07-23 14:02:01 | 2023-07-23 14:02:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> make(int a, int b, int c, int x) {
// From a 2s, b 3s, c 4s --> Make the sum x.
// Return {-1, -1, -1} if not possible.
for(int A = 0; A <= a; A++) {
for(int B = 0; B <= b; B++) {
int y = x - 2 * A - 3 * B;
if(y < 0 || y % 4 != 0 || (y / 4) > c) continue;
return {A, B, y / 4};
}
}
return {-1, -1, -1};
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
if(n == 1) {
cout << "Possible" << '\n';
cout << "R" << '\n';
continue;
}
int up = 2ll * n * (n - 1);
if(k == 1 || k == up - 1) {
cout << "Impossible" << '\n';
continue;
}
int two, three, four;
vector<vector<bool>> grid(n, vector<bool>(n));
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if((i + j) % 2 == 0) {
grid[i][j] = true;
}
}
}
if(n % 2 == 0) {
two = 2;
three = 4*((n/2) - 1);
four = n*n/2 - two - three;
} else {
two = 4;
three = 2 * (n - 3);
four = n*n/2 + 1 - two - three;
}
auto config = make(two, three, four, up - k);
if(config[0] == -1) {
assert(n % 2 == 1);
two = 0;
three = 2*(n - 1);
four = n*n/2 - two - three;
config = make(two, three, four, up - k);
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) grid[i][j] = !grid[i][j];
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == false) continue;
bool corner = (i == 0 || i == n - 1) && (j == 0 || j == n - 1);
bool side = (i == 0 || i == n - 1 || j == 0 || j == n - 1);
if(corner) {
if(config[0] > 0) {
grid[i][j] = false;
config[0]--;
}
} else if(side) {
if(config[1] > 0) {
grid[i][j] = false;
config[1]--;
}
} else {
if(config[2] > 0) {
grid[i][j] = false;
config[2]--;
}
}
}
}
cout << "Possible" << '\n';
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << (grid[i][j] ? 'B' : 'R');
}
cout << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3496kb
input:
2 3 6 3 1
output:
Possible RRB RRR BRB Impossible
result:
ok correct! (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 23ms
memory: 3480kb
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...
output:
Possible R Possible BR RB Impossible Possible RR RB Impossible Possible RR RR Possible BRB RBR BRB Impossible Possible RRB RBR BRB Possible RRR BRB RBR Possible BRB RRR BRB Possible RBR BRB RBR Possible RRB RRR BRB Possible RBR BRB RBR Possible RRR RRR BRB Possible RRR RRR RBR Possible RRR RRR RRB I...
result:
wrong answer Condition failed: "getNum(vec) == k" (test case 12)