QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#705261#6644. Red Black Gridgates_orzWA 28ms3888kbC++205.0kb2024-11-02 22:44:142024-11-02 22:44:17

Judging History

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

  • [2024-11-02 22:44:17]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:3888kb
  • [2024-11-02 22:44:14]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

typedef long long LL;
//#define int LL
#define inl inline
const int N = 3e5 + 10;
const int M = N * 2;
//const int mod=998244353;
const int mod = 1000000007;
const double eps = 1e-8;
//const int mod=1e9+7;
typedef pair<int, int> PII;
//const int INF=0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m;

void become_faster() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int a[4]={-1,0,1,0};
int b[4]={0,1,0,-1};
void solve() {
    cin>>n>>m;
    if(m==1||m==2*n*(n-1)-1) {
        cout<<"Impossible"<<"\n";
        return;
    }
    if(n<=3) {
        cout<<"Possible"<<"\n";
        if(m==0) {
            for(int i=1;i<=n;i++) {
                for(int j=1;j<=n;j++)cout<<"B"<<"\n";
                cout<<"\n";
            }
            return;
        }
        if(n==2) {
            if(m==2) {
                cout<<"RB"<<"\n";
                cout<<"BB"<<"\n";
            }
            if(m==4) {
                cout<<"RB"<<"\n";
                cout<<"BR"<<"\n";
            }
            return;
        }
        if(n==3) {
            if(m==2) {
                cout<<"RBB"<<"\n";
                cout<<"BBB"<<"\n";
                cout<<"BBB"<<"\n";
            }
            if(m==3) {
                cout<<"BBB"<<"\n";
                cout<<"RBB"<<"\n";
                cout<<"BBB"<<"\n";
            }
            if(m==4) {
                cout<<"BBB"<<"\n";
                cout<<"BRB"<<"\n";
                cout<<"BBB"<<"\n";
            }
            if(m==5) {
                cout<<"RBB"<<"\n";
                cout<<"BBR"<<"\n";
                cout<<"BBB"<<"\n";
            }
            if(m==6) {
                cout<<"RBB"<<"\n";
                cout<<"BRB"<<"\n";
                cout<<"BBB"<<"\n";
            }
            if(m==7) {
                cout<<"BRB"<<"\n";
                cout<<"BBB"<<"\n";
                cout<<"RBR"<<"\n";
            }
            if(m==8) {
                cout<<"BRB"<<"\n";
                cout<<"BBR"<<"\n";
                cout<<"RBB"<<"\n";
            }
            if(m==9) {
                cout<<"BRB"<<"\n";
                cout<<"RBR"<<"\n";
                cout<<"BBB"<<"\n";
            }
            if(m==10) {
                cout<<"RRB"<<"\n";
                cout<<"RBR"<<"\n";
                cout<<"BRB"<<"\n";
            }
            if(m==12) {
                cout<<"BRB"<<"\n";
                cout<<"RBR"<<"\n";
                cout<<"BRB"<<"\n";
            }
            return;
        }
        return;
    }
    string s[n+1];
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            s[i]=" "+s[i];
        }
        for(int j=1;j<=n;j++) {
            s[i][j]='B';
        }
    }
    int res=n*(n-1)*2;
    int sign=1;
    for(int i=1;i<=n;i++) {
        sign=i&1;
        sign^=1;
        for(int j=1;j<=n;j++) {
            if(sign)s[i][j]='R';
            sign^=1;
        }
    }
    vector<PII>num_2,num_3,num_4;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(s[i][j]=='B') {
                int cnt=0;
                for(int k=0;k<4;k++) {
                    int x=i+a[k];
                    int y=j+b[k];
                    if(x>=1&&x<=n&&y>=1&&y<=n) {
                        if(s[x][y]=='R')cnt++;
                    }
                }
                if(cnt==2)num_2.push_back({i,j});
                if(cnt==3)num_3.push_back({i,j});
                if(cnt==4)num_4.push_back({i,j});
            }
        }
    }
    /*for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++)cerr<<s[i][j];
        cerr<<"\n";
    }*/
    //cerr<<"3: ";
    //for(auto [t1,t2]:num_3)cerr<<t1<<" "<<t2<<"\n";
    int tmp=res-m;
    //cerr<<"? tmp="<<tmp<<"\n";
    if(tmp&1) {
        if(num_3.size()) {
            tmp-=3;
            auto [x,y]=num_3.back();
            num_3.pop_back();
            s[x][y]='R';
        }
    }
    //cerr<<"tmp="<<tmp<<"\n";
    int maxn=tmp/3;
    if(maxn&1)maxn--;
    if(num_3.size()&1)num_3.pop_back();
    //cerr<<"maxn="<<maxn<<"\n";
    for(int i=0;i<min((int)num_3.size(),maxn);i++) {
        auto [x,y]=num_3[i];
        s[x][y]='R';
        tmp-=3;
    }
    //cerr<<"sb: "<<tmp<<"\n";
    maxn=tmp/4;
    for(int i=0;i<min((int)num_4.size(),maxn);i++) {
        auto [x,y]=num_4[i];
        s[x][y]='R';
        tmp-=4;
    }

    maxn=tmp/2;
    for(int i=0;i<min((int)num_2.size(),maxn);i++) {
        auto [x,y]=num_2[i];
        s[x][y]='R';
        tmp-=2;
    }
    //cerr<<"tmp="<<tmp<<"\n";
    if(tmp) {
        cout<<"Impossible"<<"\n";
        return;
    }
    cout<<"Possible"<<"\n";
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++)cout<<s[i][j];
        cout<<"\n";
    }

}
/*
1
4 7

 */
signed main() {
    become_faster();
    int T = 1;
    //T=read();
    cin>>T;
    //for(int i=1;i<=100;i++)solve(i);
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3572kb

input:

2
3 6
3 1

output:

Possible
RBB
BRB
BBB
Impossible

result:

ok correct! (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 28ms
memory: 3888kb

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
B

Possible
RB
BR
Impossible
Possible
RB
BB
Impossible
Possible
B
B

B
B

Possible
BRB
RBR
BRB
Impossible
Possible
RRB
RBR
BRB
Possible
BRB
RBR
BBB
Possible
BRB
BBR
RBB
Possible
BRB
BBB
RBR
Possible
RBB
BRB
BBB
Possible
RBB
BBR
BBB
Possible
BBB
BRB
BBB
Possible
BBB
RBB
BBB
Possible
RBB
BBB
...

result:

wrong answer Condition failed: "A.length() == n" (test case 6)