QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235317 | #6644. Red Black Grid | jzh# | WA | 27ms | 3916kb | C++20 | 3.4kb | 2023-11-02 17:12:27 | 2023-11-02 17:12:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int cal(int mask) {
int cnt = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (abs(i % 3 - j % 3) + abs(i / 3 - j / 3) == 1) {
cnt += (((mask >> i) & 1) ^ (1 & (mask >> j))) != 0;
}
}
}
return cnt / 2;
}
void show(int ret) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int id = 3 * i + j;
cout << (((ret >> id) & 1) ? 'R' : 'B');
}
cout << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
unordered_map<int, int> ans;
for (int msk = 0; msk < (1 << 9); msk++) {
ans[cal(msk)] = msk;
}
while (t--) {
ll n, k;
cin >> n >> k;
if (k == 1 || 2LL * n * (n - 1) - k == 1) {
cout << "Impossible\n";
continue;
}
if (n == 2) {
if (k == 4) {
cout << "Possible\n";
cout << "RB\n";
cout << "BR\n";
} else if (k == 2) {
cout << "Possible\n";
cout << "RB\n";
cout << "RR\n";
}
continue;
}
if (n == 3) {
auto ret = ans[k];
cout << "Possible\n";
show(ret);
continue;
}
vector<vector<int>> block(n + 10, vector<int>(n + 10));
vector<pair<ll, pii>> op;
vector<pair<ll, pii>> op3;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if ((i + j) % 2 == 0) {
block[i][j] = 1;
int cnt = 4;
if (i == 0 || i == n - 1)cnt--;
if (j == 0 || j == n - 1)cnt--;
op.push_back({cnt, {i, j}});
}
}
}
for (int i = 0; i < op.size(); i++) {
if (op[i].first == 2 && i != 0) {
swap(op[0], op[i]);
}
}
for (int i = 0; i < op.size(); i++) {
if (op[i].first == 3 && i != 1) {
swap(op[1], op[i]);
}
}
for (int i = 0; i < op.size(); i++) {
if (op[i].first == 4 && i != 2) {
swap(op[2], op[i]);
}
}
ll num = 2LL * n * (n - 1) - k;
ll fir = 9;
vector<int> from(2LL * n * (n - 1) + 50, -1);
from[2] = 0, from[3] = 1, from[4] = 2;
from[5] = 1, from[7] = 1, from[9] = 1;
from[6] = 2;
for (int i = 3; i < op.size(); i++) {
auto [cnt, pos] = op[i];
for (int j = fir + cnt; j >= fir - 1; j--) {
if (from[j - cnt] == -1 || j == fir)continue;
from[j] = i;
}
fir += cnt;
}
assert(fir >= num);
while (num > 0) {
auto [cnt, pos] = op[from[num]];
num -= cnt;
block[pos.first][pos.second] = 0;
}
assert(num == 0);
cout << "Possible\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << (block[i][j] ? 'R' : 'B');
}
cout << "\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3884kb
input:
2 3 6 3 1
output:
Possible RBR BRR RRR Impossible
result:
ok correct! (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 27ms
memory: 3916kb
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 RB BR Impossible Possible RB RR Impossible Possible RBR BRB RBR Impossible Possible BRB RBR BRR Possible RBR BRB RRR Possible BRB RBR RRR Possible RRB BBR RRR Possible RBR BRR RRR Possible RRB BRR RRR Possible BRB RRR RRR Possible RBR RRR RRR Possible BRR RRR RRR Impossible Possi...
result:
wrong answer Condition failed: "A.length() == n" (test case 6)