QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104944#6394. Turn on the Lightckiseki#TL 0ms0kbC++205.7kb2023-05-12 16:11:002023-05-12 16:11:04

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-12 16:11:04]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-05-12 16:11:00]
  • 提交

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

output:


result: