Submission #807190

#TimeUsernameProblemLanguageResultExecution timeMemory
807190rxlfd314Furniture (JOI20_furniture)C++17
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; using ari2 = array<int, 2>; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<vector<bool>> bad(N+2, vector<bool>(M+2, 0)); int dcnt[N+M+1] = {}; auto yeet = [&](int X, int Y) { queue<ari2> qu; qu.push({X, Y}); dcnt[X+Y] += !bad[X][Y]; bad[X][Y] = 1; while (qu.size()) { auto [i, j] = qu.front(); qu.pop(); if (bad[i-1][j+1]) { if (!bad[i-1][j]) { qu.push({i-1, j}); dcnt[i-1+j]++; } if (!bad[i][j+1]) { qu.push({i, j+1}); dcnt[i+j+1]++; } bad[i-1][j] = bad[i][j+1] = 1; } if (bad[i+1][j-1]) { if (!bad[i][j-1]) { qu.push({i, j-1}); dcnt[i+j-1]++; } if (!bad[i+1][j]) { qu.push({i+1, j}); dcnt[i+1+j]++; } bad[i][j-1] = bad[i+1][j] = 1; } } }; for (int i = 0; i < N+2; i++) { bad[i][0] = bad[i][M+1] = 1; } for (int i = 0; i < M+2; i++) { bad[0][i] = bad[N+1][i] = 1; } for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { bool b; cin >> b; if (b) { yeet(i, j); } } } int Q; for (cin >> Q; Q--; ) { int i, j; cin >> i >> j; if (bad[i][j] || dcnt[i+j] < min(N, i+j) - max(1, i+j-M)) { yeet(i, j); cout << "1\n"; } else { cout << "0\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...