QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#127860 | #6644. Red Black Grid | 45645A | TL | 1ms | 13440kb | C++14 | 1.7kb | 2023-07-20 10:26:36 | 2023-07-20 10:26:37 |
Judging History
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...