QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134993#6644. Red Black GridDelay_for_five_minutes#WA 1ms5440kbC++203.5kb2023-08-05 10:32:102023-08-05 10:32:21

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 10:32:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5440kb
  • [2023-08-05 10:32:10]
  • 提交

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];
vector<pii> p[5];
vector<pii> e;
bool check1(){
    for(int i=2;i<=4;++i)p[i].clear();
    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);
    e.clear();
    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);
    }

    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]&&f[j-e[i].second])
                f[j]=1,pre[j]=i;
    return f[m];
}
bool check0(){
    for(int i=2;i<=4;++i)p[i].clear();
    p[2].emplace_back(1,1);
    p[2].emplace_back(n,n);
    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^1){
            p[3].emplace_back(1,i);
            p[3].emplace_back(i,1);
        }
        if((i+n)&1^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^1)
                p[4].emplace_back(i,j);
    e.clear();
    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);
    }

    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]&&f[j-e[i].second])
                f[j]=1,pre[j]=i;
    return f[m];
}
void solve(){
    cin>>n>>m;
    m=2*n*(n-1)-m;
    if(n==1){
        cout<<"Possible\n";
        cout<<"R\n";
        return;
    }

    if(check1()){
        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];
        return;
    }
    if(check0()){
        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]='R';
        }
        cout<<"Possible\n";
        for(int i=1;i<=n;++i,cout<<'\n')
            for(int j=1;j<=n;++j)
                cout<<ans[i][j];
        return;
    }
}
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: 0
Wrong Answer
time: 1ms
memory: 5440kb

input:

2
3 6
3 1

output:

Possible
BBB
BBR
BRB

result:

wrong output format Unexpected end of file - token expected (test case 2)