QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#202358#6644. Red Black Gridarseny_y#TL 0ms5492kbC++235.5kb2023-10-05 23:19:542023-10-05 23:19:55

Judging History

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

  • [2023-10-05 23:19:55]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:5492kb
  • [2023-10-05 23:19:54]
  • 提交

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 ger(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 (ger(i, j + 1, dep + 1)) return true;
        a[i][j] ^= 1;
        max -= hru2 - hru1;
        if (ger(i, j + 1, dep + 1)) return true;
    } else {
        if (ger(i, j + 1,dep + 1)) return true;
        a[i][j] ^= 1;
        max += hru2 - hru1;
        if (ger(i, j + 1, dep + 1)) return true;
        a[i][j] ^= 1;
        max -= hru2 - hru1;
    }
    return false;
}
vc<std::array<int, 3>> x;
bool da[3005 * 3005 * 2];

int cnt = 0;
int sui = 0;
bool gen(int i = 0) {
    if (cnt == k) {
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) a[i][j] = 0;
        for (int i = 0; i < x.size(); ++i) if (da[i]) a[x[i][1]][x[i][2]] = 1;
        for (int i = 0; i < n; ++i) {
            std::string s;
            for (int j = 0; j < n; ++j) s.push_back(a[i][j] ? 'R' : 'B');
            std::cout << s << '\n';
        }
        return true;
    }
    if (cnt > k) return false;
    if (i == x.size()) {
        return false;
    }
    da[i] = 1;
    cnt += x[i][0];
    if (gen(i + 1)) return true;
    da[i] = 0;
    cnt -= x[i][0];
    if (gen(i + 1)) return true;
    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;
        if (n <= 3) {

            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(ger(0, 0));
            }
            continue;
        }
        int hex = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                hex += i != n - 1;
                hex += j != n - 1;
            }
        }

        if (k > hex || k == hex - 1 || k == 1) {
            std::cout << "Impossible\n";
//            gen(0, 0);
        } else {
            std::cout << "Possible\n";
            x.clear();
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if ((i + j + 1) % 2) {
                        if (i % (n - 1) == 0 && j % (n - 1) == 0) x.push_back({2, i, j});
                        else if (i % (n - 1) == 0 || j % (n - 1) == 0) x.push_back({3, i, j});
                        else x.push_back({4, i, j});
                    }
                }
            }
            std::sort(x.begin(), x.end());
            cnt = 0;
            assert(n <= 3 || gen());
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
3 6
3 1

output:

Possible
BRR
RBR
RRR
Impossible

result:

ok correct! (2 test cases)

Test #2:

score: -100
Time Limit Exceeded

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: