QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127899#6644. Red Black Gridxjsc01RE 1ms3576kbC++232.6kb2023-07-20 11:15:142023-07-20 11:15:17

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-20 11:15:17]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3576kb
  • [2023-07-20 11:15:14]
  • 提交

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...

output:


result: