QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104944 | #6394. Turn on the Light | ckiseki# | TL | 0ms | 0kb | C++20 | 5.7kb | 2023-05-12 16:11:00 | 2023-05-12 16:11:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int cnt = sizeof...(T);
(..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L)
cerr << (f++ ? ", " : "") << *L;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
const int maxn = 100;
string a[maxn];
bool done[maxn][maxn];
int v[maxn][maxn];
constexpr int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
constexpr int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
bool solve(int u, int d, int l, int r, int n, int m) {
if (u >= d or l >= r) return true;
auto fixup = [&](int i, int j) {
cout << i << ", " << j << ":";
for (int p = 0; p < 8; ++p) {
int x = 2 * i + dx[p];
int y = 2 * j + dy[p];
if (0 > x or x >= n) continue;
if (0 > y or y >= m) continue;
cout << " " << x << "," << y;
if (x != u and x != d - 1 and y != l and y != r - 1)
v[i][j]--;
}
cout << '\n';
};
for (int i = u; i < d; ++i) {
fixup(i, l);
if (l != r - 1) fixup(i, r - 1);
}
for (int j = l + 1; j < r - 1; ++j) {
fixup(u, j);
if (u != d - 1) fixup(d - 1, j);
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cout << v[i][j] << " \n"[j == m - 1];
cout << '\n';
if (r - l > 1 and d - u > 1) {
vector<pair<int, int>> p;
for (int i = l; i + 1 < r; ++i)
p.emplace_back(u, i);
for (int i = u; i + 1 < d; ++i)
p.emplace_back(i, r - 1);
for (int i = r - 1; i > l; --i)
p.emplace_back(d - 1, i);
for (int i = d - 1; i > u; --i)
p.emplace_back(i, l);
vector<int> backup;
for (auto [x, y] : p)
backup.push_back(v[x][y]);
// 0
bool can0 = true;
{
auto [x, y] = p[0];
auto [nx, ny] = p[1];
if (v[nx][ny] == 2)
can0 = false;
}
if (can0) {
p.push_back(p[0]);
for (size_t i = 1; i + 1 < p.size(); ++i) {
auto [x, y] = p[i];
auto [nx, ny] = p[i + 1];
if (v[x][y] == 0) {
if (v[nx][ny] != 0 and v[nx][ny] != 1)
can0 = false;
break;
} else if (v[nx][ny] == 1) {
a[x + nx][y + ny] = '#';
v[nx][ny] -= 1;
} else {
can0 = false;
break;
}
}
auto [x, y] = p.back();
if (v[x][y] != 0) can0 = false;
p.pop_back();
}
if (not can0) {
for (size_t i = 0; i < p.size(); ++i) {
auto [x, y] = p[i];
v[x][y] = backup[i];
}
// 1
bool can1 = true;
{
auto [x, y] = p[0];
auto [nx, ny] = p[1];
v[x][y]--;
a[x + nx][y + ny] = '#';
v[nx][ny]--;
}
p.push_back(p[0]);
for (size_t i = 1; i + 1 < p.size(); ++i) {
auto [x, y] = p[i];
auto [nx, ny] = p[i + 1];
if (v[x][y] == 0) {
a[x + nx][y + ny] = '.';
if (v[nx][ny] != 0 and v[nx][ny] != 1)
can1 = false;
break;
} else if (v[nx][ny] == 1) {
a[x + nx][y + ny] = '#';
v[nx][ny] -= 1;
} else {
can1 = false;
break;
}
}
auto [x, y] = p.back();
if (v[x][y] != 0) can1 = false;
p.pop_back();
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cout << v[i][j] << " \n"[j == m - 1];
if (not can1) return false;
}
} else if (r - l == 1 and d - u == 1) {
if (v[u][l] != 0) return false;
} else {
vector<pair<int, int>> p;
for (int i = u; i < d; ++i)
for (int j = l; j < r; ++j)
p.emplace_back(i, j);
for (size_t i = 0; i + 1 < p.size(); ++i) {
auto [x, y] = p[i];
auto [nx, ny] = p[i + 1];
if (v[x][y] == 0) {
if (v[nx][ny] != 0 and v[nx][ny] != 1)
return false;
} else if (v[x][y] == 1) {
a[x + nx][y + ny] = '#';
v[nx][ny] -= 1;
} else {
return false;
}
}
auto [x, y] = p.back();
if (v[x][y] != 0) return false;
}
return solve(u + 1, d - 1, l + r, r - 1, n, m);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 0; i < 2 * n - 1; ++i)
cin >> a[i];
for (int i = 0; i < 2 * n - 1; i += 2)
for (int j = 0; j < 2 * m - 1; j += 2)
v[i / 2][j / 2] = a[i][j] - '0';
if (solve(0, n, 0, m, n, m)) {
cout << "YES\n";
for (int i = 0; i < 2 * n - 1; ++i)
cout << a[i] << '\n';
} else {
cout << "NO\n";
}
return 0;
}
/*
0, 0: 0,1 1,0 1,1
0, 2:
1, 0: 2,1 1,0 1,1
1, 2:
2, 0:
2, 2:
0, 1: 0,1 1,2 1,1
2, 1:
1 3 3
4 8 5
3 5 3
0 2 3
4 8 5
3 5 3
NO
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3