QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #848657 | #9884. Grid Construction | ucup-team6275 | RE | 7ms | 108756kb | C++23 | 6.8kb | 2025-01-09 00:52:45 | 2025-01-09 00:52:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for (int i = 0; i < (n); i += 1)
#define len(a) ((int)(a).size())
mt19937 rnd(234);
const ll inf = 1e18;
const int maxw = 1010;
const int maxh = 12;
char dp[maxw + 1][maxh + 1][1 << (maxh + 1)];
vector<vector<char>> mega_solve(int h, int w) {
assert(h <= maxh and w <= maxw);
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
auto bit = [&](int mask, int i) {
return ((mask >> i) & 1);
};
for (int i = 0; i < w; i += 1) {
if (i > 0) {
rep(mask, (1 << (h + 1))) {
if ((mask >> h) % 2 == 0) {
continue;
}
if (!dp[i - 1][h][mask]) {
continue;
}
int nmask = mask - (1 << h);
nmask *= 2;
dp[i][0][nmask] = true;
}
}
for (int j = 0; j < h; j += 1) {
rep(mask, (1 << (h + 1))) {
if (!dp[i][j][mask]) {
continue;
}
int a = bit(mask, j) ^ 1;
int b = bit(mask, j + 1) ^ 1;
rep(c, 2) {
rep(d, 2) {
if (a + b + c + d == 3 or a + b + c + d == 0) {
int nmask = mask;
nmask -= (nmask & (1 << j));
nmask -= (nmask & (1 << (j + 1)));
nmask += (d << j);
nmask += (c << (j + 1));
dp[i][j + 1][nmask] = true;
}
}
}
}
}
}
int cur_mask = (1 << (h + 1)) - 1;
if (!dp[w - 1][h][cur_mask]) {
return {};
}
vector<vector<char>> res(h, vector<char>(w, '.'));
for (int i = w - 1; i >= 0; i -= 1) {
assert(dp[i][h][cur_mask]);
for (int j = h - 1; j >= 0; j -= 1) {
int d = bit(cur_mask, j);
int c = bit(cur_mask, j + 1);
int gda = -1, gdb = -1;
int gdnmask = -1;
rep(a, 2) {
rep(b, 2) {
if (a + b + c + d == 3 or a + b + c + d == 0) {
int nmask = cur_mask;
nmask -= (nmask & (1 << j));
nmask -= (nmask & (1 << (j + 1)));
nmask += ((a ^ 1) << j);
nmask += ((b ^ 1) << (j + 1));
if (dp[i][j][nmask]) {
gda = a;
gdb = b;
gdnmask = nmask;
}
}
}
}
assert(gda != -1);
int a = gda;
int b = gdb;
if (a + b + c + d == 3) {
if (a == 0) {
res[j][i] = 'v';
} else if (b == 0) {
res[j][i] = '>';
} else if (c == 0) {
res[j][i] = '^';
} else {
res[j][i] = '<';
}
}
cur_mask = gdnmask;
}
assert(cur_mask % 2 == 0);
cur_mask /= 2;
cur_mask += (1 << h);
}
return res;
}
vector<vector<char>> swap_solve(int h, int w) {
if (h < w) {
return mega_solve(h, w);
}
auto res = mega_solve(w, h);
if (res.empty()) {
return res;
}
vector<vector<char>> new_res(h, vector<char>(w));
rep(i, h) {
rep(j, w) {
if (res[j][i] == '^') {
new_res[i][j] = '<';
} else if (res[j][i] == '<') {
new_res[i][j] = '^';
} else if (res[j][i] == '>') {
new_res[i][j] = 'v';
} else if (res[j][i] == 'v') {
new_res[i][j] = '>';
} else {
new_res[i][j] = res[j][i];
}
}
}
return new_res;
}
vector<vector<char>> solve(int h, int w) {
if (h % 2 != 1 or w % 2 != 1) {
return {};
}
int d = 0;
while (min(h, w) - 6 * d > maxh) {
d += 1;
}
auto res = swap_solve(h - d * 6, w - d * 6);
vector<vector<char>> new_res(h, vector<char>(w, '.'));
rep(i, h - 6 * d) {
rep(j, w - 6 * d) {
new_res[i + 3 * d][j + 3 * d] = res[i][j];
}
}
rep(step, d) {
int step3 = 3 * step;
int step6 = 6 * step;
for (int i = 1; i < h - step6; i += 1) {
new_res[i + step3][0 + step3] = 'v';
}
for (int i = 0; i + 1 < h - step6; i += 1) {
new_res[i + step3][w - 1 - step3] = '^';
}
for (int j = 0; j + 1 < w - step6; j += 1) {
new_res[0 + step3][j + step3] = '<';
}
for (int j = 1; j < w - step6; j += 1) {
new_res[h - 1 - step3][j + step3] = '>';
}
for (int i = 2; i + 2 < h - step6; i += 2) {
new_res[i + step3][1 + step3] = '>';
new_res[i + step3][w - 2 - step3] = '<';
}
for (int j = 2; j + 2 < w - step6; j += 2) {
new_res[1 + step3][j + step3] = 'v';
new_res[h - 2 - step3][j + step3] = '^';
}
for (int i = 3; i + 3 < h - step6; i += 2) {
new_res[i + step3][2 + step3] = '<';
new_res[i + step3][w - 3 - step3] = '>';
}
for (int j = 3; j + 3 < w - step6; j += 2) {
new_res[2 + step3][j + step3] = '^';
new_res[h - 3 - step3][j + step3] = 'v';
}
}
return new_res;
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int h, w;
cin >> h >> w;
auto res = solve(h, w);
if (res.empty()) {
cout << "No" << "\n";
} else {
cout << "Yes" << "\n";
rep(i, h) {
rep(j, w) {
cout << res[i][j];
}
cout << "\n";
}
}
/*
for (int h = 1; h <= maxh; h += 1) {
for (int w = 1; w <= 40; w += 1) {
auto res = mega_solve(h, w);
if (res.empty()) {
cout << "No" << "\n";
} else {
cout << h << " " << w << "\n";
rep(i, h) {
rep(j, w) {
cout << res[i][j];
}
cout << "\n";
}
cout << endl
<< "\n";
}
}
}
*/
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 108696kb
input:
3 3
output:
Yes ^>> ^.v <<v
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
4 4
output:
No
result:
ok Correct : No
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
4 5
output:
No
result:
ok Correct : No
Test #4:
score: 0
Accepted
time: 4ms
memory: 108756kb
input:
11 17
output:
Yes <<<<<<<<<<<<<<<<^ v.v.v.v.v.v.v.v.^ v>.^.^.^.<v>.^.<^ v.<<<<<^>.v.<^>.^ v>.v.v.^.<v>.^.<^ v.<v>.<^>.v.<^>.^ v>.v.^.^.^.^.^.<^ v.<v>>>>>>>>>>>.^ v>.v.v.v.v.v.v.<^ v.^.^.^.^.^.^.^.^ v>>>>>>>>>>>>>>>>
result:
ok Correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1000 1000
output:
No
result:
ok Correct : No
Test #6:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
6 6
output:
No
result:
ok Correct : No
Test #7:
score: -100
Runtime Error
input:
7 7