Submission #1342790

#TimeUsernameProblemLanguageResultExecution timeMemory
1342790po_rag526Toy (CEOI24_toy)C++20
44 / 100
438 ms35512 KiB
// BU KODU AI ILE BIRLESDIIRMISM
// MEN OJUZDA 2 defe 1 ci olaraq 35 iikinci olaraq ferqli subtusk 9 aldim 44 socre oldu
//Ancaq vjudgeda bu mukun oldagii ucun bu iki kodu gemini komeyi ile birlsdiridim her iki kod Vjudgeyede submit olunub
// Qisaca ekmemeisem



#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;
#define hurryupmrcat ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll w, h, k, l;
ll tx, ty;
ll p[1505][1505];
ll x1_start, y1_start, x2_start, y2_start;

bool v1[301][301][11][11];

bool v2[91][91][91][91];

struct Cor {
    ll x1, y1, x2, y2;
};

bool ok(ll r1, ll c1, ll r2, ll c2) {
    if (r1 < 0 || r2 >= h || c1 < 0 || c2 >= w) return false;
    ll s = p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
    return s == 0;
}

void solve1() {
    queue<Cor> q;
    ll h0 = x2_start - x1_start;
    ll v0 = y1_start - y2_start;
    
    q.push({x1_start, y1_start, x2_start, y2_start});
    v1[x1_start][y2_start][h0][v0] = true;

    ll dx[] = {1, -1, 0, 0};
    ll dy[] = {0, 0, 1, -1};

    while (!q.empty()) {
        Cor c = q.front();
        q.pop();

        if (tx >= c.x1 && tx < c.x1 + k && ty == c.y1 && ty >= c.y2 && ty < c.y2 + l && tx == c.x2) {
            cout << "YES" << endl;
            return;
        }

        for (ll i = 0; i < 4; ++i) {
            ll nx1 = c.x1 + dx[i];
            ll ny1 = c.y1 + dy[i];
            if (ok(ny1, nx1, ny1, nx1 + k - 1)) {
                if (c.x2 >= nx1 && c.x2 < nx1 + k && ny1 >= c.y2 && ny1 < c.y2 + l) {
                    ll hf = c.x2 - nx1;
                    ll vf = ny1 - c.y2;
                    if (!v1[nx1][c.y2][hf][vf]) {
                        v1[nx1][c.y2][hf][vf] = true;
                        q.push({nx1, ny1, c.x2, c.y2});
                    }
                }
            }
        }

        for (ll i = 0; i < 4; ++i) {
            ll nx2 = c.x2 + dx[i];
            ll ny2 = c.y2 + dy[i];
            if (ok(ny2, nx2, ny2 + l - 1, nx2)) {
                if (nx2 >= c.x1 && nx2 < c.x1 + k && c.y1 >= ny2 && c.y1 < ny2 + l) {
                    ll hf = nx2 - c.x1;
                    ll vf = c.y1 - ny2;
                    if (!v1[c.x1][ny2][hf][vf]) {
                        v1[c.x1][ny2][hf][vf] = true;
                        q.push({c.x1, c.y1, nx2, ny2});
                    }
                }
            }
        }
    }
    cout << "NO" << endl;
}

void solve2() {
    queue<Cor> q;
    q.push({x1_start, y1_start, x2_start, y2_start});
    v2[x1_start][y1_start][x2_start][y2_start] = true;

    ll dx[] = {1, -1, 0, 0};
    ll dy[] = {0, 0, 1, -1};

    while (!q.empty()) {
        Cor c = q.front();
        q.pop();

        if (c.x2 == tx && c.y1 == ty) {
            cout << "YES" << endl;
            return;
        }

        for (ll i = 0; i < 4; ++i) {
            ll nx = c.x1 + dx[i];
            ll ny = c.y1 + dy[i];
            if (nx >= 0 && nx + k <= w && ny >= 0 && ny < h) {
                if (ok(ny, nx, ny, nx + k - 1)) {
                    if (c.x2 >= nx && c.x2 < nx + k && ny >= c.y2 && ny < c.y2 + l) {
                        if (!v2[nx][ny][c.x2][c.y2]) {
                            v2[nx][ny][c.x2][c.y2] = true;
                            q.push({nx, ny, c.x2, c.y2});
                        }
                    }
                }
            }
        }

        for (ll i = 0; i < 4; ++i) {
            ll nx = c.x2 + dx[i];
            ll ny = c.y2 + dy[i];
            if (nx >= 0 && nx < w && ny >= 0 && ny + l <= h) {
                if (ok(ny, nx, ny + l - 1, nx)) {
                    if (nx >= c.x1 && nx < c.x1 + k && c.y1 >= ny && c.y1 < ny + l) {
                        if (!v2[c.x1][c.y1][nx][ny]) {
                            v2[c.x1][c.y1][nx][ny] = true;
                            q.push({c.x1, c.y1, nx, ny});
                        }
                    }
                }
            }
        }
    }
    cout << "NO" << endl;
}

void solve() {
    cin >> w >> h >> k >> l;
    cin >> x1_start >> y1_start >> x2_start >> y2_start;

    for (ll i = 0; i < h; ++i) {
        for (ll j = 0; j < w; ++j) {
            char ch; cin >> ch;
            p[i + 1][j + 1] = p[i][j + 1] + p[i + 1][j] - p[i][j] + (ch == 'X');
            if (ch == '*') { tx = j; ty = i; }
        }
    }

    if (w <= 90 && h <= 90) {
        solve2();
    } else {
        solve1();
    }
}

int main() {
    hurryupmrcat
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...