oj.uz

Submission #867898

# Submission time Handle Problem Language Result Execution time Memory
867898 2023-10-29T16:57:42 Z pandapythoner Furniture (JOI20_furniture) C++14
100 / 100
 338 ms 10296 KB 
#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 (1) {
        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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 11 ms 604 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 193 ms 5732 KB Output is correct
13 Correct 87 ms 3920 KB Output is correct
14 Correct 287 ms 8764 KB Output is correct
15 Correct 274 ms 8664 KB Output is correct
16 Correct 338 ms 9448 KB Output is correct
17 Correct 314 ms 9872 KB Output is correct
18 Correct 327 ms 9668 KB Output is correct
19 Correct 313 ms 10124 KB Output is correct
20 Correct 329 ms 10288 KB Output is correct
21 Correct 303 ms 10296 KB Output is correct