QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#202308 | #6644. Red Black Grid | arseny_y# | WA | 24ms | 3656kb | C++23 | 3.6kb | 2023-10-05 21:53:36 | 2023-10-05 21:53:37 |
Judging History
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);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
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)