QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#207956#6644. Red Black GridUFRJWA 28ms3736kbC++144.1kb2023-10-09 01:01:342023-10-09 01:01:34

Judging History

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

  • [2023-10-09 01:01:34]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:3736kb
  • [2023-10-09 01:01:34]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;


bool guloso(vector<vector<int>> &grid, int n, int k){

    auto isColor = [&](int i, int j, int c) -> bool {
        if(i < 0 || i >= n) return false;
        if(j < 0 || j >= n) return false;
        if(grid[i][j] == c) return true;
        return false;
    };
    using T = tuple<int, int, int>; // qtd dif, i, j
    array<int, 5> qtd = {0};
    int tot = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j<n; j++){
            if(grid[i][j]){
                tot += isColor(i-1, j, 0);
                tot += isColor(i+1, j, 0);
                tot += isColor(i, j-1, 0);
                tot += isColor(i, j+1, 0);
            } else {
                int cur = 0;
                cur += isColor(i-1, j, 1);
                cur += isColor(i+1, j, 1);
                cur += isColor(i, j-1, 1);
                cur += isColor(i, j+1, 1);
                qtd[cur]++;
            }
        }
    }
    //cout<<" total antes "<<tot<<" k "<<k<<endl;
    if(k > tot) return false;
    //cout<<"TOT "<<tot<<" "<<qtd[1]<<"\n";
    int dif = tot - k;
    vector<bool> dp(dif + 1);
    vector<pair<int, int>> link(dif + 1, {-1, -1});
    dp[0] = 1;
    for(int i = 1; i <= 4; i++){
        for(int j = dif - i; j >=0 ; j--){
            if(!dp[j]) continue;
            int k = qtd[i], s = j + i;
            int K = qtd[i];
            while(k > 0 && s <= dif && !dp[s]){
                dp[s] = 1, link[s] = {K - k + 1, i},  --k, s += i;
            }
        }
    }
    if(dp[dif]){
        vector<int> change(5);
        int j = dif;
        while(j > 0){
            auto [cur, i] = link[j];
            change[i] += cur;
            j = j - cur * i;
        }

        for(int i = 0; i<n; i++){
            for(int j = 0; j< n; j++){
                if(!grid[i][j]){
                    int cur = 0;
                    cur += isColor(i-1, j, 1);
                    cur += isColor(i+1, j, 1);
                    cur += isColor(i, j-1, 1);
                    cur += isColor(i, j+1, 1);
                    if(change[cur] > 0){
                        grid[i][j] = 1;
                        //cout<<"mudei "<<i<<" "<<j<<" "<<cur<<" "<<change[cur]<<"\n";
                        change[cur]--;
                    }
                }
            }
        }
        return true;
    }


    return false;
}

void solve(){
    int n, k;
    cin>>n>>k;
    if(n == 1){
        cout<<"Possible\n";
        cout<<"R\n";
        return;
    }
    if(k == 0){
        cout<<"Possible\n";
        for(int i = 0;i<n; i++){
            for(int j = 0; j<n; j++){
                cout<<"R";
            }
            cout<<"\n";
        }
        return;
    }
    if(k == 1){
        cout<<"Impossible\n";
        return;
    }
    else if(n == 3 && k == 5){
        cout<<"Possible\n";
        cout<<"RRR\n";
        cout<<"RBB\n";
        cout<<"RRR\n";
    }
    else {
        vector<vector<int>> grid(n, vector<int>(n));
        for(int i = 0; i<n; i++){
            for(int j = (i%2); j < n; j += 2){
                grid[i][j] = 1;
            }
        }
        if(guloso(grid, n, k)){
            cout<<"Possible\n";
            for(int i = 0; i<n; i++){
                for(int j = 0; j<n; j++){
                    if(grid[i][j]) cout<<"B";
                    else cout<<"R";
                }
                cout<<"\n";
            }
            return;
        }
        grid = vector<vector<int>>(n, vector<int>(n));
        for(int i = 0; i<n; i++){
            for(int j = !(i%2); j < n; j += 2){
                grid[i][j] = 1;
            }
        }
        if(guloso(grid, n, k)){
            cout<<"Possible\n";
            for(int i = 0; i<n; i++){
                for(int j = 0; j<n; j++){
                    if(grid[i][j]) cout<<"B";
                    else cout<<"R";
                }
                cout<<"\n";
            }
            return;
        }
        cout<<"Impossible\n";
     }
}

int main(){
    cin.tie(0)->sync_with_stdio(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: 0ms
memory: 3580kb

input:

2
3 6
3 1

output:

Possible
BBB
BBR
BRB
Impossible

result:

ok correct! (2 test cases)

Test #2:

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

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
R
Possible
BR
RB
Impossible
Possible
BB
RB
Impossible
Possible
RR
RR
Possible
BRB
RBR
BRB
Impossible
Possible
BBR
BRB
RBR
Possible
BBB
RBR
BRB
Possible
BBB
BRB
RBR
Impossible
Possible
BBB
BBR
BRB
Possible
RRR
RBB
RRR
Possible
BBB
BRB
BBB
Possible
BBB
BBB
BRB
Possible
BBB
BBB
BBR
Impossible
...

result:

wrong answer Condition failed: "A == B" (test case 12)