oj.uz

Submission #1070543

# Submission time Handle Problem Language Result Execution time Memory
1070543 2024-08-22T15:09:45 Z faruk Toy (CEOI24_toy) C++17
0 / 100
 6 ms 2904 KB 
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

vector<string> grid;
vector<vector<int> > max_up, max_right, can_hori, can_vert, box_hori, box_vert;
int n, m;

bool check_box_hori(int i, int j1, int j2) {
    j1 = max(j1, 0);
    j2 = min(j2, m - 1);
    if (j1 > j2)
        return 0;
    int v1 = box_hori[i][j1];
    if (j2 != m - 1)
        v1 -= box_hori[i][j2 + 1];
    return v1 > 0;
}

bool check_box_vert(int i1, int i2, int j) {
    i1 = max(i1, 0);
    i2 = min(i2, n - 1);
    if (i1 > i2)
        return 0;
    int v2 = box_vert[i2][j];
    if (i1 != 0)
        v2 -= box_vert[i1 - 1][j];
    return v2;
}

int get_num_ok_hori(int i, int j1, int j2) {
    j1 = max(j1, 0);
    j2 = min(j2, m - 1);
    if (j1 > j2)
        return 0;
    int v1 = can_hori[i][j1];
    if (j2 != m - 1)
        v1 -= can_hori[i][j2 + 1];
    return v1;
}

int get_num_ok_vert(int i1, int i2, int j) {
    i1 = max(i1, 0);
    i2 = min(i2, n - 1);
    if (i1 > i2)
        return 0;
    int v2 = can_vert[i2][j];
    if (i1 != 0)
        v2 -= can_vert[i1 - 1][j];
    return v2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int w, h;
    cin >> m >> n >> w >> h;
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    pii strt(y2 + h - 1, x1);

    pii endd;
    grid = vector<string>(n);
    for (int i = 0; i < n; i++)
        cin >> grid[i];
    max_up = max_right = can_hori = can_vert = box_hori = box_vert = vector<vector<int> > (n + 1, vector<int>(m + 1));
    for (int i = 0; i < n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            if (grid[i][j] == '*')
                endd = pii(i, j);
            if (grid[i][j] == '.' || grid[i][j] == '*')
                max_up[i][j] = max_right[i][j] = 1;
            if (i != 0 and max_up[i][j] != 0)
                max_up[i][j] += max_up[i - 1][j];
            if (j != m - 1 and max_up[i][j] != 0)
                max_right[i][j] += max_right[i][j + 1];
            
            if (max_up[i][j] >= h)
                can_vert[i][j] = 1;
            if (max_right[i][j] >= w)
                can_hori[i][j] = 1;

            if (j != m - 1)
                if (can_vert[i][j] and can_vert[i][j + 1])
                    box_vert[i][j] = 1;
            if (i != 0)
                if (can_hori[i - 1][j] and can_hori[i][j])
                    box_hori[i][j] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            if (j != m - 1)
                box_hori[i][j] += box_hori[i][j + 1], can_hori[i][j] += can_hori[i][j + 1];
            if (i != 0)
                box_vert[i][j] += box_vert[i - 1][j], can_vert[i][j] += can_vert[i - 1][j];
        }
    }

    vector<vector<bool> > vis(n, vector<bool> (m));
    vis[strt.first][strt.second] = true;

    queue<pii> qu;
    qu.push(strt);
    while (!qu.empty()) {
        pii curr = qu.front(); qu.pop();

        // try moving vert to front
        int i1 = curr.first, i2 = curr.first + h - 1;
        if (curr.second != m - 1 and !vis[curr.first][curr.second + 1] and check_box_vert(i1, i2, curr.second))
        {
            // add anoterh
            if (get_num_ok_hori(curr.first, curr.second - (w - 1) - 1, curr.second) > 0) {
                vis[curr.first][curr.second + 1] = true;
                qu.push(pii(curr.first, curr.second + 1));
            }
        }
        // try moving back
        if (curr.second != 0 and !vis[curr.first][curr.second - 1] and check_box_vert(i1, i2, curr.second - 1))
        {
            // add anotehr
            if (get_num_ok_hori(curr.first, curr.second - (w - 1), curr.second - 1) > 0) {
                vis[curr.first][curr.second - 1] = true;
                qu.push(pii(curr.first, curr.second - 1));
            }
        }

        // try moving hori up
        int j1 = curr.second - w + 1, j2 = curr.second;
        if (curr.first != 0 and !vis[curr.first - 1][curr.second] and check_box_hori(curr.first, j1, j2)) {
            if (get_num_ok_vert(curr.first, curr.first + (h - 2), curr.second) > 0) {
                vis[curr.first - 1][curr.second] = true;
                qu.push(pii(curr.first - 1, curr.second));
            }
        }

        // try moving hori down
        if (curr.first != n - 1 and !vis[curr.first + 1][curr.second] and check_box_hori(curr.first + 1, j1, j2)) {
            if (get_num_ok_vert(curr.first + 1, curr.first + (h - 1), curr.second) > 0) {
                vis[curr.first + 1][curr.second] = true;
                qu.push(pii(curr.first + 1, curr.second));
            }
        }
    }

    
    if (vis[endd.first][endd.second])   
        cout << "YES\n";
    else
        cout << "NO\n";
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 2 ms 2876 KB Output is correct
15 Correct 3 ms 2652 KB Output is correct
16 Correct 3 ms 2396 KB Output is correct
17 Correct 3 ms 2644 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Correct 4 ms 2824 KB Output is correct
20 Correct 4 ms 2652 KB Output is correct
21 Correct 4 ms 2652 KB Output is correct
22 Correct 4 ms 2652 KB Output is correct
23 Correct 4 ms 2652 KB Output is correct
24 Correct 6 ms 2904 KB Output is correct
25 Correct 4 ms 2652 KB Output is correct
26 Correct 3 ms 2652 KB Output is correct
27 Correct 3 ms 2652 KB Output is correct
28 Correct 3 ms 2652 KB Output is correct
29 Correct 3 ms 2652 KB Output is correct
30 Correct 3 ms 2652 KB Output is correct
31 Correct 3 ms 2652 KB Output is correct
32 Correct 3 ms 2836 KB Output is correct
33 Correct 3 ms 2424 KB Output is correct
34 Correct 3 ms 2608 KB Output is correct
35 Correct 3 ms 2664 KB Output is correct
36 Incorrect 2 ms 2652 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -