#include <bits/stdc++.h>
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
class rep {
struct Iter {
usize itr;
constexpr Iter(const usize pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
constexpr usize operator*() const noexcept { return itr; }
};
const Iter first, last;
public:
explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter end() const noexcept { return last; }
};
template <class F> struct RecursiveLambda : private F {
explicit constexpr RecursiveLambda(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <class F> constexpr decltype(auto) rec_lambda(F&& f) {
using G = std::decay_t<F>;
return RecursiveLambda<G>(std::forward<G>(f));
}
template <class T> using Vec = std::vector<T>;
constexpr isize dx[] = {0, 1, 0, -1};
constexpr isize dy[] = {1, 0, -1, 0};
void JOI20_furniture_main() {
usize N, M;
std::cin >> N >> M;
Vec<Vec<char>> grid(N, Vec<char>(M));
for (auto& v : grid) {
for (auto& x : v) {
std::cin >> x;
}
}
Vec<Vec<bool>> alive(N, Vec<bool>(M));
{
Vec<Vec<int>> state(N, Vec<int>(M));
Vec<Vec<bool>> done(N, Vec<bool>(M));
std::queue<std::pair<isize, isize>> que;
const auto push = [&](const isize i, const isize j) {
if (i >= 0 and j >= 0 and i < (isize)N and j < (isize)M and grid[i][j] == '0' and !done[i][j]) {
done[i][j] = true;
que.emplace(i, j);
}
};
push(0, 0);
while (!que.empty()) {
const auto [i, j] = que.front();
que.pop();
state[i][j] |= 1;
for (const auto k : rep(0, 2)) {
push(i + dx[k], j + dy[k]);
}
}
done = Vec<Vec<bool>>(N, Vec<bool>(M));
push(N - 1, M - 1);
while (!que.empty()) {
const auto [i, j] = que.front();
que.pop();
state[i][j] |= 2;
for (const auto k : rep(2, 4)) {
push(i + dx[k], j + dy[k]);
}
}
for (const auto i : rep(0, N)) {
for (const auto j : rep(0, M)) {
if (state[i][j] == 3) {
alive[i][j] = true;
}
}
}
}
Vec<usize> min(N), max(N);
for (const auto i : rep(0, N)) {
min[i] = 0;
while (!alive[i][min[i]]) {
min[i] += 1;
}
max[i] = M - 1;
while (!alive[i][max[i]]) {
max[i] -= 1;
}
}
const auto disable = rec_lambda([&](auto&& dfs, const isize i, const isize j) -> void {
if (!alive[i][j]) {
return;
}
alive[i][j] = false;
while (!alive[i][min[i]]) {
min[i] += 1;
}
max[i] = M - 1;
while (!alive[i][max[i]]) {
max[i] -= 1;
}
for (const auto k : rep(0, 4)) {
const auto ni = i + dx[k];
const auto nj = j + dy[k];
if (ni < 0 or nj < 0 or ni >= (isize)N or nj >= (isize)M) {
continue;
}
if (ni == 0 and nj == 0) {
continue;
}
if (ni == (isize)N - 1 and nj == (isize)M - 1) {
continue;
}
if ((ni == 0 or !alive[ni - 1][nj]) and (nj == 0 or !alive[ni][nj - 1])) {
dfs(ni, nj);
}
if ((ni == (isize)N - 1 or !alive[ni + 1][nj]) and (nj == (isize)M - 1 or !alive[ni][nj + 1])) {
dfs(ni, nj);
}
}
});
usize Q;
std::cin >> Q;
while (Q--) {
usize i, j;
std::cin >> i >> j;
i -= 1;
j -= 1;
if (!alive[i][j]) {
std::cout << 1 << '\n';
continue;
}
const usize up = (i == 0 ? 0 : max[i - 1]);
const usize down = (i + 1 == N ? M - 1 : min[i + 1]);
if (up <= j and j <= down) {
std::cout << 0 << '\n';
continue;
}
std::cout << 1 << '\n';
disable(i, j);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
JOI20_furniture_main();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
4 ms |
460 KB |
Output is correct |
| 5 |
Correct |
5 ms |
448 KB |
Output is correct |
| 6 |
Correct |
6 ms |
460 KB |
Output is correct |
| 7 |
Correct |
5 ms |
460 KB |
Output is correct |
| 8 |
Correct |
5 ms |
460 KB |
Output is correct |
| 9 |
Correct |
5 ms |
460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
4 ms |
460 KB |
Output is correct |
| 5 |
Correct |
5 ms |
448 KB |
Output is correct |
| 6 |
Correct |
6 ms |
460 KB |
Output is correct |
| 7 |
Correct |
5 ms |
460 KB |
Output is correct |
| 8 |
Correct |
5 ms |
460 KB |
Output is correct |
| 9 |
Correct |
5 ms |
460 KB |
Output is correct |
| 10 |
Correct |
10 ms |
844 KB |
Output is correct |
| 11 |
Correct |
4 ms |
460 KB |
Output is correct |
| 12 |
Correct |
355 ms |
10152 KB |
Output is correct |
| 13 |
Correct |
68 ms |
6884 KB |
Output is correct |
| 14 |
Correct |
467 ms |
14716 KB |
Output is correct |
| 15 |
Correct |
481 ms |
14716 KB |
Output is correct |
| 16 |
Correct |
381 ms |
16084 KB |
Output is correct |
| 17 |
Correct |
644 ms |
16824 KB |
Output is correct |
| 18 |
Correct |
555 ms |
16392 KB |
Output is correct |
| 19 |
Correct |
545 ms |
17364 KB |
Output is correct |
| 20 |
Correct |
720 ms |
17396 KB |
Output is correct |
| 21 |
Correct |
444 ms |
17380 KB |
Output is correct |
