QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#128041#6644. Red Black GridhinayahhTL 0ms3440kbC++172.9kb2023-07-20 15:03:502023-07-20 15:03:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-20 15:03:51]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3440kb
  • [2023-07-20 15:03:50]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long 
#define pii pair<int, int> 
#define pll pair<long, long>
#define _max(x, y) x = max(x, y)
using namespace std;
const int N = 1e3 + 10;
int n, k;
char G[N][N];
int c2, c3, c4;
vector<pii> p2, p3, p4;
int read(){
    char ch = 0; int x = 0,f = 1;
    while(ch<'0' || ch>'9'){if(ch=='-')f = -1;ch = getchar();}
    while(ch>='0'&&ch<='9'){x = x*10 + ch-'0';ch = getchar();}
    return x*f;
}

bool Try(bool x) {
    c2 = 0, c3 = 0, c4 = 0;
    p2.clear(); p3.clear(); p4.clear();
    for(int i=1; i<=n; i++) 
        for(int j=1; j<=n; j++) {
            if(((i+j)&1) == x) {
                if((i == 1 || i == n) && (j == 1 || j == n)) p2.push_back({i, j});
                else if(i == 1 || i == n || j == 1 || j == n) p3.push_back({i, j});
                else p4.push_back({i, j});
            }
        }

    c4 = min(k/4, (int)p4.size());
    c2 = (k-c4*4)*2;
    c3 = -(k-c4*4);
    
    while(c3 < 0 || c2 > p2.size()) c2 -= 3, c3 += 2;

    if(c2 > p2.size() || c3 > p3.size() || c2 < 0 || c3 < 0) { 
        c4--;
        c2 = (k-c4*4)*2;
        c3 = -(k-c4*4);
        while(c3 < 0 || c2 > p2.size()) c2 -= 3, c3 += 2;
    }

    if(c2 > p2.size() || c3 > p3.size() || c2 < 0 || c3 < 0) return false;
    return true;
}


void solve() {
    n = read(); k = read(); 
    if(k == 1 || k == 2*(n*n-n)-1 || k > 2*(n*n-n)) { puts("Impossible"); return; }
    else puts("Possible");

    if(n <= 3) {
        if(k == 2) { puts("RBB"); puts("BBB"); puts("BBB"); return; }
        if(k == 3) { puts("BBB"); puts("RBB"); puts("BBB"); return; }
        if(k == 4) { puts("BBB"); puts("BRB"); puts("BBB"); return; }
        if(k == 5) { puts("RBB"); puts("BBR"); puts("BBB"); return; }
        if(k == 6) { puts("BBB"); puts("RBR"); puts("BBB"); return; }
        if(k == 7) { puts("RBR"); puts("BBB"); puts("BRB"); return; }
        if(k == 8) { puts("RBR"); puts("BBB"); puts("RBR"); return; }
        if(k == 9) { puts("BRB"); puts("RBR"); puts("BBB"); return; }
        if(k == 10) { puts("RBR"); puts("BRB"); puts("RBB"); return; }
        if(k == 12) { puts("RBR"); puts("BRB"); puts("RBR"); return; }
    }


    for(int i=1; i<=n; i++) 
        for(int j=1; j<=n; j++) 
            G[i][j] = 'B';

    if(!Try(0)) Try(1);

    for(int i=0; i<c3; i++) {
        auto [x, y] = p3[i];
        G[x][y] = 'R';
    }

    for(int i=0; i<c2; i++) {
        auto [x, y] = p2[i];
        G[x][y] = 'R';
    }

    for(int i=0; i<c4; i++) {
        auto [x, y] = p4[i];
        G[x][y] = 'R';
    }

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) printf("%c", G[i][j]);
        puts("");
    }

}

int main() {
	#ifdef LOCAL
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif

    int T = read();

    while(T--) solve();



}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
3 6
3 1

output:

Possible
BBB
RBR
BBB
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...

output:


result: