QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202358 | #6644. Red Black Grid | arseny_y# | TL | 0ms | 5492kb | C++23 | 5.5kb | 2023-10-05 23:19:54 | 2023-10-05 23:19:55 |
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 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());
}
}
}
详细
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...