QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207962#6644. Red Black GridUFRJWA 23ms3936kbC++144.2kb2023-10-09 01:10:442023-10-09 01:10:44

Judging History

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

  • [2023-10-09 01:10:44]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:3936kb
  • [2023-10-09 01:10:44]
  • 提交

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 || k == n * (n-1)*2 - 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();
    }
}

详细

Test #1:

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

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: 23ms
memory: 3936kb

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)