QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#127899 | #6644. Red Black Grid | xjsc01 | RE | 1ms | 3576kb | C++23 | 2.6kb | 2023-07-20 11:15:14 | 2023-07-20 11:15:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
inline int cal(int u, int v){
int ans = 0;
for(int k = 0; k < 4; k++){
int x = u+dx[k];
int y = v+dy[k];
if(x < 1 || x > n || y < 1 || y > n) continue;
ans ++;
}
return ans;
}
char ran[3000][3000];
void judged(int std){
// for(int i = 1; i <= n; i++)
// for(int j = 1; j <= n; j++)
// putchar(ran[i][j]);
int ans = 0;
for(int u = 1; u <= n; u++){
for(int v = 1; v <= n; v++){
for(int k = 0; k < 4; k++){
int x = u+dx[k];
int y = v+dy[k];
if(x < 1 || x > n || y < 1 || y > n) continue;
if(ran[u][v] == 'R' && ran[x][y] == 'B') ans++;
}
}
}
//cout << ans<< endl;
assert(std == ans);
}
void solve(int &cnt2, int &cnt3, int &cnt4, int n, int m){
cnt2 = cnt3 = cnt4 = 0;
int tot4 = 0, tot2 = 0, tot3 = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if((i+j)&1) continue;
int ret = cal(i, j);
if(ret == 2) tot2++;
else if(ret == 3) tot3++;
else if(ret == 4) tot4++;
}
}
int sub = 2*n*(n-1) - m;
if(sub & 1)
tot3--, cnt3++, sub-=3;
{
int can = tot3/2;
int di_num = min(can, sub/6);
cnt3 += di_num * 2;
tot3 -= di_num * 2;
sub -= di_num * 6;
}
if(!sub) return ;
{
int can = tot4;
int di_num = min(can, sub/4);
cnt4 += di_num;
tot4 -= di_num;
sub -= di_num * 4;
}
if(!sub) return ;
{
int can = tot2;
int di_num = min(can, sub/2);
cnt2 += di_num;
tot2 -= di_num;
sub -= di_num * 2;
}
}
int main()
{
int T;
cin >> T;
while(T--){
scanf("%d%d", &n, &m);
int tot = 2*n*(n-1);
if(n == 1 && m >= 1) puts("Impossible");
else if(m == 1 || m == tot - 1){
puts("Impossible");
}
else if(m > tot) {
puts("Impossible");
}
else {
puts("Possible");
int cnt2, cnt3, cnt4;
solve(cnt2, cnt3, cnt4, n, m);
// cout << "tot" << tot<<" \n";
// cout << "cnt:" << cnt2 << " "<<cnt3<<" "<<cnt4<<endl;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if((i+j)&1){
putchar('B');
ran[i][j] = 'B';
}
else{
int ret = cal(i, j);
if(ret == 2){
if(cnt2) putchar('B'),ran[i][j] = 'B', cnt2--;
else putchar('R'),ran[i][j] = 'R';
}
else if(ret == 3){
if(cnt3) putchar('B'),ran[i][j] = 'B', cnt3--;
else putchar('R'),ran[i][j] = 'R';
}
else{
if(cnt4) putchar('B'),ran[i][j] = 'B', cnt4--;
else putchar('R'),ran[i][j] = 'R';
}
}
}
puts("");
}
judged(m);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
input:
2 3 6 3 1
output:
Possible BBR BBB RBR Impossible
result:
ok correct! (2 test cases)
Test #2:
score: -100
Dangerous Syscalls
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...