Submission #867868

#	Time	Username	Problem	Language	Result	Execution time	Memory
867868		pandapythoner	Furniture (JOI20_furniture)	C++14	0 / 100	1 ms	348 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;

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    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;
    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;
        }
        if (((!is_ok(nx - 1, ny) || a[nx - 1][ny]) && (!is_ok(nx, ny - 1) || a[nx][ny - 1])) ||
            ((!is_ok(nx + 1, ny) || a[nx + 1][ny]) && (!is_ok(nx, ny + 1) || a[nx][ny + 1]))) {
            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();
            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();
    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 (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();
    }
    for (int i = 0; i < qrs; i += 1) {
        cout << rs[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

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

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