QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122773#6644. Red Black Gridwnmrmr#RE 1ms3396kbC++232.4kb2023-07-11 03:08:522023-07-11 03:08:55

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-11 03:08:55]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3396kb
  • [2023-07-11 03:08:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) //cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl

#define pb push_back
// #define int long long

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int n, k;

void solve () {
    cin >> n >> k;

    int mx = 2 * (n - 1) * n;

    if (k == 1 || k == mx - 1) {
        cout << "Impossible\n";
        return;
    }

    vector ans (n, vector<int> (n));

    cout << "Possible\n";
    if (k < n * (n - 1)) {
        int i = 0;
        while (k > n) {
            for (int j = 0; j < n; j++) ans[i][j]++;
            if (i) k -= n;
            i += 2;
            k -= n;
        }
        if (k > 0) {
            for (int j = 0; j < k - 1; j++) ans[i][j]++;
        }
    }
    else if (k >= n * (n - 1)) {
        // se for maior que a metade
        // vamos quadricular
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) ans[i][j] = (i + j) & 1;

        vector<pair<int, int>> adj[5];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) if (!ans[i][j]) {
                int vis = 0;
                for (int p = 0; p < 4; p++) {
                    int ii = i + dx[p], jj = j + dy[p];
                    if (ii < 0 || ii >= n || jj < 0 || jj >= n) continue;
                    vis++;
                }
                // dbg (vis);
                adj[vis].pb ({i, j});
            }

        auto paint = [&] (int id) {
            auto [x, y] = adj[id].back (); adj[id].pop_back ();
            ans[x][y] ^= 1;
        };

        if (k & 1) {
            paint (3);
        }
        while (k > 6) {
            if (adj[3].size () < 2) break;
            paint (3);
            paint (3);
            k -= 6;
        }
        while (k > 2) {
            if (adj[4].size () == 0) break;
            paint (4);
            k -= 4;
        }
        if (k == 2) paint (2);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (ans[i][j]) cout << 'R';
            else cout << 'B';
        }
        cout << "\n";
    }
}

signed main () {
    ios::sync_with_stdio(0);cin.tie(0);
    int t; cin >> t;
    while (t--)
        solve ();
}

详细

Test #1:

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

input:

2
3 6
3 1

output:

Possible
BRB
RRR
BRR
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: