oj.uz

답안 #867896

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867896 2023-10-29T16:57:13 Z pandapythoner Furniture (JOI20_furniture) C++14
100 / 100
 657 ms 19840 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 (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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 4 ms 528 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 5 ms 524 KB Output is correct
6 Correct 6 ms 604 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 6 ms 604 KB Output is correct
9 Correct 7 ms 600 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 4 ms 528 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 5 ms 524 KB Output is correct
6 Correct 6 ms 604 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 6 ms 604 KB Output is correct
9 Correct 7 ms 600 KB Output is correct
10 Correct 21 ms 856 KB Output is correct
11 Correct 5 ms 572 KB Output is correct
12 Correct 367 ms 9792 KB Output is correct
13 Correct 158 ms 5716 KB Output is correct
14 Correct 554 ms 16472 KB Output is correct
15 Correct 516 ms 16724 KB Output is correct
16 Correct 539 ms 18156 KB Output is correct
17 Correct 594 ms 19160 KB Output is correct
18 Correct 624 ms 18612 KB Output is correct
19 Correct 629 ms 19828 KB Output is correct
20 Correct 613 ms 19796 KB Output is correct
21 Correct 657 ms 19840 KB Output is correct