QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134900 | #6644. Red Black Grid | Delay_for_five_minutes# | RE | 1ms | 5508kb | C++20 | 2.0kb | 2023-08-05 09:50:33 | 2023-08-05 09:50:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1003,M=2e6+3;
int n,m;
bool f[M];
int pre[M];
char ans[N][N];
void solve(){
cin>>n>>m;
vector<pii> p[5];
if(n==1){
cout<<"Possible\n";
cout<<"R\n";
return;
}
else{
if(!(n&1)){
p[2].emplace_back(1,n);
p[2].emplace_back(n,1);
}
for(int i=2;i<n;++i){
if((i+1)&1){
p[3].emplace_back(1,i);
p[3].emplace_back(i,1);
}
if((i+n)&1){
p[3].emplace_back(n,i);
p[3].emplace_back(i,n);
}
}
for(int i=2;i<n;++i)
for(int j=2;j<n;++j)
if((i+j)&1)
p[4].emplace_back(i,j);
}
vector<pii> e;
for(int i=2;i<=4;++i){
int t=p[i].size(),bit=0;
while(1<<bit<=t)e.emplace_back(i,i<<bit),t-=1<<bit,++bit;
if(t)e.emplace_back(i,i*t);
}
// for(int i=0;i<e.size();++i)cout<<e[i].first<<' '<<e[i].second<<'\n';
m=2*n*(n-1)-m;
memset(f,0,sizeof(bool)*(m+1));
f[0]=1;
for(int i=0;i<e.size();++i)
for(int j=m;j>=e[i].second;--j)
if(f[j-e[i].second])
f[j]=1,pre[j]=i;
if(!f[m]){
cout<<"Impossible\n";
return;
}
int cnt[5];
memset(cnt,0,sizeof(cnt));
while(m){
cnt[e[pre[m]].first]+=e[pre[m]].second/e[pre[m]].first;
m-=e[pre[m]].second;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
ans[i][j]=(i+j)&1?'R':'B';
for(int i=2;i<=4;++i){
for(int j=0;j<cnt[i];++j)
ans[p[i][j].first][p[i][j].second]='B';
}
cout<<"Possible\n";
for(int i=1;i<=n;++i,cout<<'\n')
for(int j=1;j<=n;++j)
cout<<ans[i][j];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5508kb
input:
2 3 6 3 1
output:
Possible BBB BBR BRB Impossible
result:
ok correct! (2 test cases)
Test #2:
score: -100
Runtime Error
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...