QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#135315 | #6644. Red Black Grid | salvator_noster# | TL | 44ms | 3604kb | C++14 | 2.7kb | 2023-08-05 13:44:11 | 2023-08-05 13:44:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
using ll = long long;
int rd(){
int x;
scanf("%d",&x);
return x;
}
int A[105][105],ans[105][105];
int main(){
memset(ans,-1,sizeof ans);
rep(n,1,3){
int S=(1<<(n*n))-1;
rep(s,0,S){
rep(i,1,n){
rep(j,1,n){
if((1<<((i-1)*n+j-1))&s){
A[i][j]=0;
}else A[i][j]=1;
}
}
int res=0;
rep(i,1,n)rep(j,1,n){
if(i!=n)if(A[i+1][j]==A[i][j])res++;
if(j!=n)if(A[i][j]==A[i][j+1])res++;
}
ans[n][res]=s;
}
}
rep(cas,1,rd()){
int n=rd(),m=2*n*(n-1)-rd();
bool fl=0;
if(n<=3){
int s=ans[n][m];
if(s==-1){
puts("Impossible");
}else{
rep(i,1,n){
rep(j,1,n){
if((1<<((i-1)*n+j-1))&s){
A[i][j]=0;
}else A[i][j]=1;
}
}
puts("Possible");
rep(i,1,n){
rep(j,1,n)printf("%c",A[i][j]?'B':'R');
puts("");
}
}
continue;
}
int cnt2=0,cnt3=0,cnt4=0;
rep(i,1,n)rep(j,1,n){
if((i+j)&1){
if((i==1||i==n)&&(j==1||j==n))
cnt2++;
else if((i==1||i==n)||(j==1||j==n))
cnt3++;
else cnt4++;
}
}
drep(t4,min(cnt4,m/4),0)rep(t2,0,cnt2)rep(t3,0,cnt3){
if(fl)continue;
int C2=t2,C3=t3,C4=t4;
if(C2*2+C3*3+C4*4==m){
fl=1;
puts("Possible");
rep(i,1,n){
rep(j,1,n){
if((i+j)&1){
if((i==1||i==n)&&(j==1||j==n)){
if(C2)printf("B"),C2--;
else printf("R");
}
else if(((i==1||i==n)||(j==1||j==n))){
if(C3)printf("B"),C3--;
else printf("R");
}
else {
if(C4)printf("B"),C4--;
else printf("R");
}
}else printf("B");
}
puts("");
}
}
}
cnt2=cnt3=cnt4=0;
rep(i,1,n)rep(j,1,n){
if(((i+j)&1)==0){
if((i==1||i==n)&&(j==1||j==n))
cnt2++;
else if((i==1||i==n)||(j==1||j==n))
cnt3++;
else cnt4++;
}
}
drep(t4,min(m/4,cnt4),0)rep(t2,0,cnt2)rep(t3,0,cnt3){
if(fl)continue;
int C2=t2,C3=t3,C4=t4;
if(C2*2+C3*3+C4*4==m){
fl=1;
puts("Possible");
rep(i,1,n){
rep(j,1,n){
if(((i+j)&1)==0){
if((i==1||i==n)&&(j==1||j==n)){
if(C2)printf("B"),C2--;
else printf("R");
}
else if(((i==1||i==n)||(j==1||j==n))){
if(C3)printf("B"),C3--;
else printf("R");
}
else {
if(C4)printf("B"),C4--;
else printf("R");
}
}else printf("B");
}
puts("");
}
}
}
if(!fl){
//if(m!=2*n*(n-1)-1&&m!=1)cout<<n<<" "<<m<<"-------"<<endl;
puts("Impossible");
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
input:
2 3 6 3 1
output:
Possible RBR BRR RRR Impossible
result:
ok correct! (2 test cases)
Test #2:
score: 0
Accepted
time: 44ms
memory: 3604kb
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:
Possible R Possible RB BR Impossible Possible BR RR Impossible Possible RR RR Possible RBR BRB RBR Impossible Possible BRB RBR BRR Possible RBR BRB RRR Possible BRB RBR RRR Possible RRB BBR RRR Possible RBR BRR RRR Possible RRB BRR RRR Possible BRB RRR RRR Possible RBR RRR RRR Possible BRR RRR RRR I...
result:
ok correct! (4424 test cases)
Test #3:
score: -100
Time Limit Exceeded
input:
1 1000 0
output:
Possible BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...