QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497860 | #9164. Toy | Qwerty1232# | 0 | 1ms | 3844kb | C++23 | 2.9kb | 2024-07-29 19:38:21 | 2024-07-29 19:38:21 |
answer
#include <bits/stdc++.h>
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::swap(n, m);
int K, L;
std::cin >> K >> L;
std::pair<int, int> ph, pv;
std::cin >> ph.first >> ph.second >> pv.first >> pv.second;
std::swap(ph.first, ph.second);
std::swap(pv.first, pv.second);
std::vector<std::string> input(n);
for (auto& s : input) {
std::cin >> s;
}
std::pair<int, int> tg;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (input[i][j] == '*') {
tg = {i, j};
}
}
}
std::vector<std::vector<int>> prf(n + 1, std::vector<int>(m + 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
prf[i + 1][j + 1] = (input[i][j] == 'X') + prf[i][j + 1] + prf[i + 1][j] - prf[i][j];
}
}
auto get_sum = [&](char tp, std::pair<int, int> p) {
std::pair<int, int> p2(p.first + (tp == 'h' ? 1 : K), p.second + (tp == 'h' ? L : 1));
if (p.first < 0 || p.second < 0 || n < p2.first || m < p2.second) {
return 1;
}
int res = prf[p2.first][p2.second] - prf[p.first][p2.second] - prf[p2.first][p.second] + prf[p.first][p.second];
return res;
};
auto check_tg = [&](char tp, std::pair<int, int> p) {
std::pair<int, int> p2(p.first + (tp == 'h' ? 1 : K), p.second + (tp == 'h' ? L : 1));
if (p.first < 0 || p.second < 0 || n < p2.first || m < p2.second) {
return false;
}
return p.first <= tg.first && tg.first < p2.first && p.second <= tg.second && tg.second < p2.second;
};
std::vector<int> rv(n * m), rh(n * m);
for (char ch : std::string{"vh"}) {
auto& vec = ch == 'h' ? rh : rv;
std::vector<int> stack;
stack.push_back((ch == 'h') ? ph.first * m + ph.second : pv.first * m + pv.second);
while (stack.size()) {
int v = stack.back();
stack.pop_back();
if (!vec[v]) {
vec[v] = 1;
auto [x, y] = div(v, m);
for (auto [dx, dy] : std::array<std::pair<int, int>, 4>{{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}}) {
int x2 = x + dx, y2 = y + dy;
if (get_sum(ch, {x2, y2}) == 0) {
stack.push_back(x2 * m + y2);
}
}
}
}
}
bool suc1 = false, suc2 = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
suc1 |= rv[i * m + j] && check_tg('v', {i, j});
suc2 |= rh[i * m + j] && check_tg('h', {i, j});
}
}
if (suc1 && suc2) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3844kb
input:
32 16 23 15 3 8 4 1 ................................ ................................ ................................ ................................ ................................ *............................... ................................ ................................ ...................
output:
NO
result:
wrong answer expected YES, found NO
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #89:
score: 0
Wrong Answer
time: 1ms
memory: 3704kb
input:
105 31 8 4 70 27 75 26 ......................................................................................................... ......................................................................................................... ....................................................................
output:
NO
result:
wrong answer expected YES, found NO
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%