제출 #1342867

#제출 시각아이디문제언어결과실행 시간메모리
1342867AzeTurk810Toy (CEOI24_toy)C++20
0 / 100
1596 ms14008 KiB
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <cassert>
#include <iostream>

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif

constexpr int N = 1000 + 505;

struct point {
    int x, y;
};

int _h, _w, _k, _l;
point leftm, topm, intersect, fs;
char g[N][N], used[N][N];
point pref[N][N], suff[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

inline void systemd() {
    for (size_t i = 0; i <= _h + 2; i++) {
        for (size_t j = 0; j <= _w + 2; j++) {
            used[i][j] = false;
            suff[i][j].x = _h + 1;
            suff[i][j].y = _w + 1;
        }
    }
}

inline void build() {
    for (size_t i = 1; i <= _h; i++) {
        for (size_t j = 1; j <= _w; j++) {
            if (g[i][j] == 'X') {
                cerr << i << '|' << j << ln;
                pref[i][j].x = i;
                pref[i][j].y = j;
            } else {
                pref[i][j].x = pref[i - 1][j].x;
                pref[i][j].y = pref[i][j - 1].y;
            }
        }
    }

    for (int i = _h; i >= 1; --i) {
        for (int j = _w; j >= 1; --j) {
            if (g[i][j] == 'X') {
                suff[i][j].x = i;
                suff[i][j].y = j;
            } else {
                suff[i][j].x = suff[i + 1][j].x;
                suff[i][j].y = suff[i][j + 1].y;
            }
        }
    }
}

char valid(point v) {
    return (1 <= v.x && v.x <= _h && 1 <= v.y && v.y <= _w);
}

char can(point v, point u) {
    point lv = pref[v.x][v.y];
    point rv = suff[v.x][v.y];
    point lu = pref[u.x][u.y];
    point ru = suff[u.x][u.y];
    cerr << v.x << ' ' << v.y << ' ' << lv.x << ' ' << lv.y << ' ' << rv.x << ' ' << rv.y << ln;
    cerr << u.x << ' ' << u.y << ' ' << lu.x << ' ' << lu.y << ' ' << ru.x << ' ' << ru.y << ln;
    { /// can fit at u
        if (ru.x - lu.x + 1 < _k || ru.y - lu.y + 1 < _l) {
            return false;
        }
    }

    { /// find if it can go to u;
        if (!(((lv.x >= lu.x && lv.y >= lu.x) || (rv.x <= ru.x && rv.y <= ru.x))))
            return false;
    }

    return true;
}

void dfs(point v) {
    cerr << v.x << ' ' << v.y << ln;
    used[v.x][v.y] = true;

    for (int _ = 0; _ < 4; _++) {
        point u;
        u.x = v.x + dx[_], u.y = v.y + dy[_];
        if ((!valid(u)) || used[u.x][u.y] || !can(v, u))
            continue;
        dfs(u);
    }
}

char solve() {
    if (!(cin >> _w >> _h >> _k >> _l)) {
        return 1;
    }

    cin >> leftm.y >> leftm.x >> topm.y >> topm.x;
    leftm.x++;
    leftm.y++;
    topm.x++;
    topm.y++;

    systemd();
    for (size_t i = 1; i <= _h; i++) {
        for (size_t j = 1; j <= _w; j++) {
            cin >> g[i][j];
            if (g[i][j] == '*') {
                fs.x = i;
                fs.y = j;
            }
        }
    }

    { /// find intersection point
        intersect.x = topm.x;
        intersect.y = leftm.y;
        cerr << intersect.x << ' ' << intersect.y << ln;
    }

    build();

    dfs(intersect);

    if (used[fs.x][fs.y]) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
    return 0;
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1e9;
    // cin >> t;
    for (int cases = 0; cases < t; cases++) {
        if (solve())
            break;
#ifdef ONPC
        cerr << "__________\n";
#endif
    }
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
#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...