QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127860#6644. Red Black Grid45645ATL 1ms13440kbC++141.7kb2023-07-20 10:26:362023-07-20 10:26:37

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 10:26:37]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:13440kb
  • [2023-07-20 10:26:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
inline int read()
{
	char ch;
	while((ch=getchar())<'0'||ch>'9');
	int res=ch-'0';
	while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
	return res;
}
int n,K,a[N][N];
bool dfs(int x,int y,int now)
{
	if(now>K) return 0;
	if(x==n)
	{
		if(now==K)
		{
			for(int i=0;i<n;printf("\n"),i++)
				for(int j=0;j<n;j++)
				printf("%c",a[i][j]?'R':'B');
			return 1;
		}
		return 0;
	}
	a[x][y]=0;
	int tmp=now+(x&&a[x-1][y]!=a[x][y])+(y&&a[x][y-1]!=a[x][y]);
	if(y==n-1?dfs(x+1,0,tmp):dfs(x,y+1,tmp)) return 1;
	a[x][y]=1;
	tmp=now+(x&&a[x-1][y]!=a[x][y])+(y&&a[x][y-1]!=a[x][y]);
	if(y==n-1?dfs(x+1,0,tmp):dfs(x,y+1,tmp)) return 1;
	return 0;
}
struct node{
	int x,y;
	node(int a=0,int b=0){
		x=a,y=b;
	}
};
int val(node u){
	return 4-(u.x==0||u.x==n-1)-(u.y==0||u.y==n-1); 
}
bool operator<(node a,node b){ return val(a)<val(b); }
priority_queue<node>Q;
node stk[N*N];
int main()
{
	int T=read();
	while(T--)
	{
		n=read(),K=read();
		if(K==1||K==2*(n-1)*n-1) printf("Impossible\n");
		else
		{
			printf("Possible\n");
			if(n<=3) dfs(0,0,0);
			else
			{
				while(!Q.empty()) Q.pop();
				for(int i=0;i<n;i++)
					for(int j=0;j<n;j++)
					{
						a[i][j]=0;
						if(!((i+j)&1)) Q.push(node(i,j));
					}
				int top=0;
				while(K)
				{
					node tmp=Q.top();Q.pop();
					if(val(tmp)>K&&K>1) continue;
					if(K==1) K+=val(stk[top--]);
					stk[++top]=tmp;
					K-=val(tmp);			
				}
				for(int i=1;i<=top;i++) a[stk[i].x][stk[i].y]=1;				
				for(int i=0;i<n;printf("\n"),i++)
					for(int j=0;j<n;j++)
					printf("%c",a[i][j]?'R':'B');
			}
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 13440kb

input:

2
3 6
3 1

output:

Possible
BBB
BBR
BRB
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...

output:


result: