QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202308#6644. Red Black Gridarseny_y#WA 24ms3656kbC++233.6kb2023-10-05 21:53:362023-10-05 21:53:37

Judging History

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

  • [2023-10-05 21:53:37]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:3656kb
  • [2023-10-05 21:53:36]
  • 提交

answer

//I wrote this code 4 u today
#include <bits/stdc++.h>

template<class t> using vc = std::vector<t>;

#define nd node*
#define pnd pair<nd, nd>

//using namespace std;
typedef long long ll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

std::pair<int, int> q[4] = {{0,  1},
                            {1,  0},
                            {0,  -1},
                            {-1, 0}};

int a[3005][3005];
int max = 0;

int n, k;

int lz = 0;
bool gen(int i, int j, int dep = 0) {
    if (dep > 6) return false;
    if (j == n) ++i, j = 0;
    if (i == n) {
        return false;
    }
    if (max < k) return false;
    if (max == k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) std::cout << (a[i][j] ? 'B' : 'R');
            std::cout << '\n';
        }
        return true;
    }
    int hru1 = 0;
    for (auto [d1, d2]: q) {
        int i1 = i + d1, j1 = j + d2;
        if (i1 != -1 && j1 != -1 && i1 != n && j1 != n) hru1 += a[i][j] != a[i1][j1];
    }
    a[i][j] ^= 1;
    int hru2 = 0;
    for (auto [d1, d2]: q) {
        int i1 = i + d1, j1 = j + d2;
        if (i1 != -1 && j1 != -1 && i1 != n && j1 != n) hru2 += a[i][j] != a[i1][j1];
    }
    a[i][j] ^= 1;
    if (hru2 < hru1) {
        max += hru2 - hru1;
        a[i][j] ^= 1;
        if (gen(i, j + 1, dep + 1)) return true;
        a[i][j] ^= 1;
        max -= hru2 - hru1;
        if (gen(i, j + 1, dep + 1)) return true;
    } else {
        if (gen(i, j + 1,dep + 1)) return true;
        a[i][j] ^= 1;
        max += hru2 - hru1;
        if (gen(i, j + 1, dep + 1)) return true;
        a[i][j] ^= 1;
        max -= hru2 - hru1;
    }
    return false;
}

bool heh(int cnt) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            a[i][j] = 0;
            if ((i + j) % 2 && cnt) {
                --cnt;
                a[i][j] = 1;
            }
        }
    }
    max = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            max += (j + 1 != n && a[i][j] != a[i][j + 1]) + (i + 1 != n && a[i][j] != a[i + 1][j]);
        }
    }
    return max >= k;
}

int main() {
    std::cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t;
    std::cin >> t;
    while (t--) {
        max = 0;
        std::cin >> n >> k;
        int hex = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                a[i][j] = 0;
                if (max < k && (i + j) % 2) {
                    a[i][j] = 1;
                }
                hex += i != n - 1;
                hex += j != n - 1;
            }
        }
        int lo = -1, hi = n * n + 5;
        while (hi - lo > 1) {
            int mi = (lo + hi) / 2;
            if (heh(mi)) hi = mi;
            else lo = mi;
        }
        heh(hi);
//        std::cout << max << '\n';
        if (k > hex || k == hex - 1 || k == 1) {
            std::cout << "Impossible\n";
//            gen(0, 0);
        } else {
            std::cout << "Possible\n";
            gen(0, 0);
        }
    }
}

詳細信息

Test #1:

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

input:

2
3 6
3 1

output:

Possible
RBR
BRR
RRR
Impossible

result:

ok correct! (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 24ms
memory: 3656kb

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

result:

wrong answer Condition failed: "A.length() == n" (test case 11)