QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431545#6644. Red Black Griducup-team3215#RE 0ms3732kbC++232.1kb2024-06-05 18:19:132024-06-05 18:19:14

Judging History

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

  • [2024-06-05 18:19:14]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3732kb
  • [2024-06-05 18:19:13]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using pii = array<int, 2>;


int n;
vector<string> gr;
int check(int x, int y, int bad) {
    return 0 <= x && x < n && 0 <= y && y < n ? (gr[x][y] == 'B' ? 1 : bad) : 0;
}

vector<int> dx = {-1, 1, 0, 0};
vector<int> dy = {0, 0, -1, 1};

int count(int x, int y, int bad) {
    int res = 0;
    for (int k = 0; k < 4; ++k) {
        res += check(x + dx[k], y + dy[k], bad);
    }
    return res;
}

void solve() {
    int k;
    cin >> n >> k;
    if (k == 1 || k + 1 == 2 * n * (n - 1)) {
        cout << "Impossible\n";
        return;
    }
    gr.assign(n, string(n, 'B'));
    vector<vector<pii> > st(5);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            st[count(i, j, -1)].push_back({i, j});
        }
    }
    int rk = 0;
    while (rk < k) {
        int delta = min(k - rk, 4);
        int d = -1;
        for (int i = 4; i > 0; --i) {
            if (st[i].empty()) {
                continue;
            }
            if ((d == -1 && rk + i + 1 < k) || rk + i == k) {
                d = i;
            }
        }
        assert(d != -1);
        auto [x, y] = st[d].back();
        st[d].pop_back();
        int c = count(x, y, -1);
        if (c != d) {
            if (c > 0) {
                st[c].push_back({x, y});
            }
            continue;
        }
        rk += d;
        gr[x][y] = 'R';
    }
    if (rk == k) {
        cout << "Possible\n";
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (gr[i][j] == 'R') ans += count(i, j, 0);
            }
        }
        for (string & el : gr) {
            cout << el << '\n';
        }
        if (ans != k) {
            cout << n << ' ' << k << endl;
            assert(ans == k);
        }
        return;
    }
    cout << n << ' ' << k << endl;
    assert(false);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(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: 3732kb

input:

2
3 6
3 1

output:

Possible
BBB
BRB
BBR
Impossible

result:

ok correct! (2 test cases)

Test #2:

score: -100
Runtime Error

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: