QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#127373 | #6644. Red Black Grid | Ethan_xu# | WA | 15ms | 3524kb | C++20 | 5.8kb | 2023-07-19 16:29:20 | 2023-07-19 16:29:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int ans[N][N];
int n, k, prek;
bool check(int x, int y) {
if(x < 1 || y < 1 || x > n || y > n) return false;
return true;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int change(int x, int y) {
int pre = 0;
int nxt = 0;
for(int i = 0; i < 4; i++) {
if(check(x + dx[i], y + dy[i]) && ans[x + dx[i]][y + dy[i]] != ans[x][y]) pre++;
if(check(x + dx[i], y + dy[i]) && ans[x + dx[i]][y + dy[i]] == ans[x][y]) nxt++;
}
return nxt - pre;
}
void verify() {
int res = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if(i != 1 && ans[i][j] != ans[i - 1][j]) res++;
if(j != 1 && ans[i][j] != ans[i][j - 1]) res++;
}
assert(res == prek);
}
void print(int opt) {
cout << "Possible\n";
for (int i = 1; i <= n; i++, cout << "\n")
for (int j = 1; j <= n; j++) {
if (opt) ans[i][j] ^= ((i + j) & 1);
if (ans[i][j] == 0) cout << "R";
else cout << "B";
}
verify();
}
int main() {
#ifdef _DEBUG
freopen("data.txt", "r", stdin);
freopen("data.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--) {
cin >> n >> k;
prek = k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) ans[i][j] = 0;
if(n <= 3) {
int flag = 1;
for(int i = 0; i < (1 << (n * n)); i ++) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) ans[i][j] = 0;
int res = 0;
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++) {
int num = j * n + k;
int d = ((i >> num) & 1);
if(d) res += change(j + 1, k + 1);
ans[j + 1][k + 1] = d;
}
if(res == k) {
flag = 0;
print(0);
break;
}
}
if(flag == 1) cout << "Impossible\n";
continue;
}
if(k == 1) {
cout << "Impossible\n";
continue;
} else {
if(k <= n * (n - 1)) {
if (k == 0) {
print(0);
continue;
} else {
int flag = 1;
for (int i = 1; i <= n && flag; i += 2) {
for (int j = 1; j <= n && flag; j++) {
int d = change(i, j);
int cnt = 0;
if(d == 0) continue;
if(d == 3) {
ans[1][n - 1] ^= 1;
ans[1][n - 2] ^= 1;
cnt = 2;
d = 1;
}
else if(d == 2 && !(i == 1 && j == 1)) {
ans[1][n - 1] ^= 1;
cnt = 1;
d = 1;
}
ans[i][j] ^= 1;
k -= d;
if(cnt == 2 && k >= 1) {
ans[1][n - 2] ^= 1;
k--;
cnt--;
}
if(cnt == 1 && k >= 1) {
ans[1][n - 1] ^= 1;
k --;
cnt --;
}
if(k == 0) {
print(0);
flag = 0;
}
}
}
}
} else {
k = 2 * n * (n - 1) - k;
if (k == 0) {
print(1);
continue;
} else {
int flag = 1;
for (int i = 1; i <= n && flag; i += 2) {
for (int j = 1; j <= n && flag; j++) {
int d = change(i, j);
int cnt = 0;
if(d == 0) continue;
if(d == 3) {
ans[1][n - 1] ^= 1;
ans[1][n - 2] ^= 1;
cnt = 2;
d = 1;
}
else if(d == 2 && !(i == 1 && j == 1)) {
ans[1][n - 1] ^= 1;
cnt = 1;
d = 1;
}
ans[i][j] ^= 1;
k -= d;
if(cnt == 2 && k >= 1) {
ans[1][n - 2] ^= 1;
k--;
cnt--;
}
if(cnt == 1 && k >= 1) {
ans[1][n - 1] ^= 1;
k --;
cnt --;
}
if(k == 0) {
print(1);
flag = 0;
}
}
}
}
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3448kb
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: 15ms
memory: 3524kb
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 BR RR Impossible Possible RR RR 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 I...
result:
wrong answer Condition failed: "A == B" (test case 21)