QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127853#6644. Red Black GridoreoioiwyWA 28ms3604kbC++173.1kb2023-07-20 10:00:292023-07-20 10:00:30

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 10:00:30]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:3604kb
  • [2023-07-20 10:00:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// #define tpyeinput int
// inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
// inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}

template<typename T>
void read(T &x) {
    int f = 1;
    x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
}

const int N = 1e3+10, M = 2*N;
int n, k;
int g[N][N];
int mv[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

bool check(int t) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(t>>(i*n+j)&1) g[i+1][j+1] = 1;
            else g[i+1][j+1] = 0;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int k = 0; k < 4; k++) {
                int nx = i+mv[k][0], ny = j+mv[k][1];
                if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
                if(g[i][j] != g[nx][ny]) cnt++;
            }
        }
    }
    return cnt == 2*k;
}

void solve() {
    read(n), read(k);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            g[i][j] = 0;
        }
    }
    if(k == 1 || k == 2*n*(n-1)-1) {
        puts("Impossible");
        return;
    }
    bool flag = false;
    if(n <= 3) {
        int cnt = 0;
        for(int i = 0; i <= (1<<(n*n)); i++) {
            if(check(cnt+i)) {
                flag = true;
                break;
            }
        }
        if(flag) {
            puts("Possible");
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    printf("%c", g[i][j] ? 'R' : 'B');
                }
                puts("");
            }
            return;
        }
        else {
            puts("Impossible");
            return;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i&1 ? 1 : 2; j <= n; j+=2) {
            int mark = 0;
            if(i > 1 && i < n && j > 1 && j < n)
                mark = 4;
            else if(i == 1 && j == 1 || i == n && j== n)
                mark = 2;
            else
                mark = 3;
            if(k == mark+1)
                continue;
            else if(k >= mark) {
                k -= mark;
                g[i][j] = 1;
            }
            if(k == 0)
                break;
        }
    }
    puts("Possible");
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            printf("%c", g[i][j] ? 'R' : 'B');
        }
        puts("");
    }
}

int main() {
#ifdef LOCAL_TEST
    freopen("test.in", "r", stdin);
#endif
    int times = 1;
    read(times);
    while(times--) {
        solve();   
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3604kb

input:

2
3 6
3 1

output:

Possible
BRB
RBB
BBB
Impossible

result:

ok correct! (2 test cases)

Test #2:

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

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
BR
RB
Impossible
Possible
RB
BB
Impossible
Possible
BB
BB
Possible
BRB
RBR
BRB
Impossible
Possible
RBR
BRB
RBB
Possible
BRB
RBR
BBB
Possible
RBR
BRB
BBB
Possible
BBR
RRB
BBB
Possible
BRB
RBB
BBB
Possible
BBR
RBB
BBB
Possible
RBR
BBB
BBB
Possible
BRB
BBB
BBB
Possible
RBB
BBB
BBB
I...

result:

wrong answer Condition failed: "getNum(vec) == k" (test case 45)