QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202322#6644. Red Black Gridarseny_y#RE 0ms3624kbC++233.6kb2023-10-05 22:09:292023-10-05 22:09:29

Judging History

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

  • [2023-10-05 22:09:29]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3624kb
  • [2023-10-05 22:09:29]
  • 提交

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 hra = false;
bool gen(int i, int j, int dep = 0) {
    if (dep > 10) 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;
        }
        hi += 3;
        hi = std::min(hi, n * n / 2);
        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";
            assert(gen(0, 0));
        }
    }
}

詳細信息

Test #1:

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

input:

2
3 6
3 1

output:

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

Possible
R
Possible
RB
BR
Impossible
Possible
BB
BR
Impossible
Possible
RR
RR
Possible
RBR
BRB
RBR
Impossible
Possible
BBR
BRB
RBR
Possible
BRR
BRB
RBR
Possible
BRR
RRB
RBR
Possible
BRR
RRB
BRR
Possible
BRR
RBR
RRR
Possible
BRR
RRR
RBR
Possible
BRR
RRR
BRR
Possible
BRR
BRR
BRR
Possible
BRR
RRR
RRR
I...

result: