Submission #867896

#	Time	Username	Problem	Language	Result	Execution time	Memory
867896		pandapythoner	Furniture (JOI20_furniture)	C++14	100 / 100	657 ms	19840 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(234);
const ll inf = 1e18;

void print(vector<vector<int>> &a) {
    int n = (int)a.size();
    int m = (int)a[0].size();
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < m; j += 1) {
            cout << a[i][j];
        }
        cout << "\n";
    }
    cout << "\n\n";
}

int32_t main() {
    if (0) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
#ifdef LOCAL
    freopen("test", "r", stdin);
#endif
    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n, vector<int>(m, 0));
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < m; j += 1) {
            cin >> a[i][j];
        }
    }
    vector<int> cnt_gd(n + m, 0);
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < m; j += 1) {
            if (a[i][j] == 0) {
                cnt_gd[i + j] += 1;
            }
        }
    }
    int qrs;
    cin >> qrs;
    vector<vector<pair<int, int>>> go2 = {{make_pair(0, 1), make_pair(1, 0)}, {make_pair(0, -1), make_pair(-1, 0)}};
    auto is_ok = [&](int i, int j) {
        return 0 <= i && i < n && 0 <= j && j < m;
    };
    auto is_bad = [&](int nx, int ny) {
        if (nx == 0 && ny == 0) {
            return false;
        }
        if (nx == n - 1 && ny == m - 1) {
            return false;
        }
        for (auto dgo : go2) {
            int cntbd = 0;
            for (auto [dx, dy] : dgo) {
                int nnx = nx + dx;
                int nny = ny + dy;
                if (!is_ok(nnx, nny)) {
                    cntbd += 1;
                } else if (a[nnx][nny]) {
                    cntbd += 1;
                }
            }
            if (cntbd >= 2) {
                return true;
            }
        }
        return false;
    };

    queue<pair<int, int>> q;
    vector<pair<int, int>> go = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < m; j += 1) {
            if (a[i][j]) {
                continue;
            }
            if (is_bad(i, j)) {
                q.push(make_pair(i, j));
            }
        }
    };
    auto serve_queue = [&] {
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            if (a[x][y]) {
                continue;
            }
            cnt_gd[x + y] -= 1;
            a[x][y] = 1;
            for (auto [dx, dy] : go) {
                int nx = x + dx;
                int ny = y + dy;
                if (!is_ok(nx, ny) || a[nx][ny]) {
                    continue;
                }
                if (is_bad(nx, ny)) {
                    q.push(make_pair(nx, ny));
                }
            }
        }
    };
    serve_queue();

    if (n >= 100 || m >= 100) {
        // return 0;
    }
    vector<int> rs(qrs);
    for (int itr = 0; itr < qrs; itr += 1) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        // rs[itr] = itr % 2;
        // continue;
        if (cnt_gd[x + y] < 1) {
            assert(0);
        }
        if (a[x][y]) {
            rs[itr] = 1;
            continue;
        }
        if (cnt_gd[x + y] == 1) {
            rs[itr] = 0;
            continue;
        }
        rs[itr] = 1;
        q.push(make_pair(x, y));
        serve_queue();

        // cout << itr << ":\n";
        // print(a);
    }
    for (int i = 0; i < qrs; i += 1) {
        cout << rs[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

furniture.cpp: In lambda function:
furniture.cpp:65:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |             for (auto [dx, dy] : dgo) {
      |                       ^
furniture.cpp: In lambda function:
furniture.cpp:95:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |             auto [x, y] = q.front();
      |                  ^
furniture.cpp:102:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |             for (auto [dx, dy] : go) {
      |                       ^

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95