結果
| 問題 | No.1434 Make Maze |
| ユーザー |
 sten_san
|
| 提出日時 | 2023-04-22 18:22:53 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 56 ms / 2,000 ms |
| コード長 | 6,312 bytes |
| コンパイル時間 | 2,702 ms |
| コンパイル使用メモリ | 219,652 KB |
| 最終ジャッジ日時 | 2025-02-12 13:07:24 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct iofast_t {iofast_t() {ios::sync_with_stdio(false);cin.tie(nullptr);}} iofast;struct uns_t {} uns;template <typename Element, typename Head, typename ...Args>auto vec(Element init, Head arg, Args ...args) {if constexpr (sizeof...(Args) == 0) return vector(arg, init);else return vector(arg, vec(init, args...));}template <typename Element, typename Head, typename ...Args>auto vec(uns_t, Head arg, Args ...args) {return vec(Element(), arg, args...);}template <typename Container>auto distance(const Container &c, decltype(begin(c)) iter) {return distance(begin(c), iter);}template <typename RIter, typename Compare = less<typename iterator_traits<RIter>::value_type>>auto isort(RIter first, RIter last, Compare comp = Compare()) {vector<int> i(distance(first, last));iota(begin(i), end(i), 0);sort(begin(i), end(i), [&](auto x, auto y) {return comp(*(first + x), *(first + y));});return i;}template <typename, template <typename> typename, typename = void_t<>>struct detect : false_type {};template <typename T, template <typename> typename Check>struct detect<T, Check, void_t<Check<T>>> : true_type {};template <typename T, template <typename> typename Check>constexpr inline bool detect_v = detect<T, Check>::value;template <typename T>using has_member_sort = decltype(declval<T>().sort());template <typename Container, typename Compare = less<typename Container::value_type>>auto sorted(Container c, Compare comp = Compare()) {if constexpr (detect_v<Container, has_member_sort>) {c.sort(comp);return c;}else {sort(begin(c), end(c), comp);return c;}}template <typename Container, typename Compare = equal_to<typename Container::value_type>>auto uniqued(Container c, Compare comp = Compare()) {c.erase(unique(begin(c), end(c), comp), end(c));return c;}template <typename T, typename Compare = less<T>>T &chmin(T &l, T r, Compare &&f = less<T>()) { return l = min(l, r, f); }template <typename T, typename Compare = less<T>>T &chmax(T &l, T r, Compare &&f = less<T>()) { return l = max(l, r, f); }template <typename F>constexpr auto fix(F &&f) noexcept {return [f = std::tuple<F>(std::forward<F>(f))](auto &&...args) mutable {return std::get<0>(f)(fix(std::get<0>(f)), std::forward<decltype(args)>(args)...);};}#include <atcoder/dsu>int main() {constexpr int step[4][2] = {{ 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }};int h, w, x; cin >> h >> w >> x;if (x < h + w - 2 || x % 4 != (h + w - 2) % 4) {cout << -1 << endl;return 0;}const int max = [&]() {const int p = (h + 1) / 2 * (w + 1) / 2;if (h % 4 == 3 && w % 4 == 3) {return (p - 1) * 2 - 1;}return p * 2 - 1;}();if (max <= x) {cout << -1 << endl;return 0;}auto path = fix([](auto path, int h, int w, int x) -> vector<tuple<int, int>> {if (h % 2 == 0 && w % 2 != 0) {auto f = path(w, h, x);for (auto &[y, x] : f) {swap(y, x);}return f;}auto max_path = [](int h, int w) -> vector<tuple<int, int>> {auto p = vec(make_tuple(0, 0), 0);for (int i = 0; i < h - (h % 2 == 0) * 2; ++i) {for (int j = 0; j < w; ++j) {if (i % 2 == 0) {p.emplace_back(i, j);}if (i % 2 == 1) {p.emplace_back(i, w - j - 1);}}}if (h % 2 == 1) {return p;}p.emplace_back(h - 2, 0);for (int i = 1; i < w; ++i) {for (int j = 0; j < 2; ++j) {if (i % 2 == 0) {p.emplace_back(h - 1 - j, i);}if (i % 2 == 1) {p.emplace_back(h - 2 + j, i);}}}return p;};auto f = max_path(h, w);auto g = vec(make_tuple(0, 0), 0);auto vis = vec<bool>(false, h, w);int ly = -1, lx = -1;for (auto [fy, fx] : f) {int d = h + w - 2 - fy - fx;g.emplace_back(fy, fx);vis[fy][fx] = true;if (x == d) {tie(ly, lx) = { fy, fx };break;}--x;}if (ly + 1 < h && !vis[ly + 1][lx]) {while (ly + 1 < h) {g.emplace_back(++ly, lx);}}if (lx + 1 < w && !vis[ly][lx + 1]) {while (lx + 1 < w) {g.emplace_back(ly, ++lx);}}while (ly + 1 < h) {g.emplace_back(++ly, lx);}while (lx + 1 < w) {g.emplace_back(ly, ++lx);}return g;});atcoder::dsu dsu(h * w);auto ans = vec(string(w, '#'), h);auto p = path((h + 1) / 2, (w + 1) / 2, x / 2);int py = -1, px = -1;for (auto [y, x] : p) {y *= 2; x *= 2;ans[y][x] = '.';dsu.merge(0, y * w + x);if (0 <= min(py, px)) {int dy = (y - py) / 2, dx = (x - px) / 2;int ny = py + dy, nx = px + dx;ans[ny][nx] = '.';dsu.merge(0, ny * w + nx);}tie(py, px) = { y, x };}for (int i = 0; i < h; i += 2) {for (int j = 0; j < w; j += 2) {ans[i][j] = '.';for (auto [dy, dx] : step) {int ny = i + dy * 2, nx = j + dx * 2;if (min(ny, nx) < 0 || h <= ny || w <= nx) {continue;}if (!dsu.same(i * w + j, ny * w + nx)) {dsu.merge(i * w + j, ny * w + nx);ans[ny][nx] = ans[ny - dy][nx - dx] = '.';}}}}for (auto &s : ans) {cout << s << '\n';}cout << flush;}