QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#128041 | #6644. Red Black Grid | hinayahh | TL | 0ms | 3440kb | C++17 | 2.9kb | 2023-07-20 15:03:50 | 2023-07-20 15:03:51 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<long, long>
#define _max(x, y) x = max(x, y)
using namespace std;
const int N = 1e3 + 10;
int n, k;
char G[N][N];
int c2, c3, c4;
vector<pii> p2, p3, p4;
int read(){
char ch = 0; int x = 0,f = 1;
while(ch<'0' || ch>'9'){if(ch=='-')f = -1;ch = getchar();}
while(ch>='0'&&ch<='9'){x = x*10 + ch-'0';ch = getchar();}
return x*f;
}
bool Try(bool x) {
c2 = 0, c3 = 0, c4 = 0;
p2.clear(); p3.clear(); p4.clear();
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
if(((i+j)&1) == x) {
if((i == 1 || i == n) && (j == 1 || j == n)) p2.push_back({i, j});
else if(i == 1 || i == n || j == 1 || j == n) p3.push_back({i, j});
else p4.push_back({i, j});
}
}
c4 = min(k/4, (int)p4.size());
c2 = (k-c4*4)*2;
c3 = -(k-c4*4);
while(c3 < 0 || c2 > p2.size()) c2 -= 3, c3 += 2;
if(c2 > p2.size() || c3 > p3.size() || c2 < 0 || c3 < 0) {
c4--;
c2 = (k-c4*4)*2;
c3 = -(k-c4*4);
while(c3 < 0 || c2 > p2.size()) c2 -= 3, c3 += 2;
}
if(c2 > p2.size() || c3 > p3.size() || c2 < 0 || c3 < 0) return false;
return true;
}
void solve() {
n = read(); k = read();
if(k == 1 || k == 2*(n*n-n)-1 || k > 2*(n*n-n)) { puts("Impossible"); return; }
else puts("Possible");
if(n <= 3) {
if(k == 2) { puts("RBB"); puts("BBB"); puts("BBB"); return; }
if(k == 3) { puts("BBB"); puts("RBB"); puts("BBB"); return; }
if(k == 4) { puts("BBB"); puts("BRB"); puts("BBB"); return; }
if(k == 5) { puts("RBB"); puts("BBR"); puts("BBB"); return; }
if(k == 6) { puts("BBB"); puts("RBR"); puts("BBB"); return; }
if(k == 7) { puts("RBR"); puts("BBB"); puts("BRB"); return; }
if(k == 8) { puts("RBR"); puts("BBB"); puts("RBR"); return; }
if(k == 9) { puts("BRB"); puts("RBR"); puts("BBB"); return; }
if(k == 10) { puts("RBR"); puts("BRB"); puts("RBB"); return; }
if(k == 12) { puts("RBR"); puts("BRB"); puts("RBR"); return; }
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
G[i][j] = 'B';
if(!Try(0)) Try(1);
for(int i=0; i<c3; i++) {
auto [x, y] = p3[i];
G[x][y] = 'R';
}
for(int i=0; i<c2; i++) {
auto [x, y] = p2[i];
G[x][y] = 'R';
}
for(int i=0; i<c4; i++) {
auto [x, y] = p4[i];
G[x][y] = 'R';
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) printf("%c", G[i][j]);
puts("");
}
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int T = read();
while(T--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3440kb
input:
2 3 6 3 1
output:
Possible BBB RBR BBB Impossible
result:
ok correct! (2 test cases)
Test #2:
score: -100
Time Limit Exceeded
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...