Submission #1045998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045998		VahanAbraham	Toy (CEOI24_toy)	C++17	14 / 100	1600 ms	50248 KiB

Main

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <bitset>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <cassert>

using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout);

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 400;
const ll oo = 100000000000000000, MOD = 1000000007;

struct cord {
    int x, y;
};

char grid[N][N];
bool normalahor[N][N], normalaver[N][N];
int w, h, k, l, xend, yend;
map <pair<int, pair<int, pair<int, int>>>, bool> ok;

int dxhor[3] = { 1,-1,0 };
int dxver[3] = { 1,-1,0 };
int dyhor[3] = { 1,-1,0 };
int dyver[3] = { 1,-1,0 };

queue<pair<cord, cord>> q;

pair<int, int> hatvumen(cord hor, cord ver) {
    for (int i = ver.x; i <= ver.x; ++i) {
        if (hor.y >= ver.y && hor.y <= ver.y + l - 1 && i >= hor.x && i <= hor.x + k - 1) {
            return { i,hor.y };
        }
    }
    return{ -1,-1 };
}

bool mejnahor(cord hor) {
    if (hor.x >= 0 && hor.x + k - 1 <= w - 1 && hor.y >= 0 && hor.y <= h - 1) {
        return true;
    }
    return false;
}

bool mejnaver(cord ver) {
    if (ver.x >= 0 && ver.x <= w - 1 && ver.y >= 0 && ver.y + l - 1 <= h - 1) {
        return true;
    }
    return false;
}

bool normalhor(cord hor) {
    for (int i = hor.x; i <= hor.x + k - 1; ++i) {
        if (grid[hor.y][i] == 'X') {
            return false;
        }
    }
    return true;
}

bool normalver(cord ver) {
    for (int i = ver.y; i <= ver.y + l - 1; ++i) {
        if (grid[i][ver.x] == 'X') {
            return false;
        }
    }
    return true;
}

bool stug(cord hor1, cord ver1) {
    if (mejnahor(hor1) == 1 && mejnaver(ver1) == 1 && normalahor[hor1.x][hor1.y] == 1 && normalaver[ver1.x][ver1.y] == 1) {
        pair<int, int> p = hatvumen(hor1, ver1);
        if (p.fr == xend && p.sc == yend) {
            return true;
        }
        else {
            if (p.fr != -1) {
                if (ok[{hor1.x, { hor1.y,{ver1.x,ver1.y} }}] != 1) {
                    ok[{hor1.x, { hor1.y,{ver1.x,ver1.y} }}] = 1;
                    q.push({ hor1,ver1 });
                    return false;
                }
                return false;
            }
            return false;
        }
        return false;
    }
    return false;
}


void solve() {
    cin >> w >> h >> k >> l;
    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;
    cord hor, ver;
    hor.x = xh;
    hor.y = yh;
    ver.x = xv;
    ver.y = yv;
    ok[{hor.x, { hor.y,{ver.x,ver.y} }}] = 1;
    q.push({ hor,ver });
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == '*') {
                xend = j, yend = i;
            }
        }
    }
    /*cout << xend << " " << yend << endl;
    cord vv;
    vv.x = 1, vv.y = 0;
    cout << normalver(vv) << endl;*/
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cord yy;
            yy.x = j, yy.y = i;
            if (mejnaver(yy)) {
                normalaver[j][i] = normalver(yy);
            }
            if (mejnahor(yy)) {
                normalahor[j][i] = normalhor(yy);
            }
        }
    }
    if (stug(hor, ver) == 1) {
        cout << "YES" << endl;
        return;
    }
    while (q.empty() != 1) {
        hor = q.front().fr;
        ver = q.front().sc;
        //cout << hor.x << " " << hor.y << " " << ver.x << " " << ver.y << endl;
        q.pop();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                cord hor1 = hor, ver1 = ver;
                hor1.x += dxhor[i];
                ver1.x += dxver[j];
                if (hor1.x == hor.x && hor1.y == hor.y && ver.y == ver1.y && ver1.x == ver.x) {
                    continue;
                }
                if (stug(hor1, ver1)) {
                    //cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
                    cout << "YES" << endl;
                    return;
                }
            }
            for (int j = 0; j < 3; ++j) {
                cord hor1 = hor, ver1 = ver;
                hor1.x += dxhor[i];
                ver1.y += dyver[j];
                if (hor1.x == hor.x && hor1.y == hor.y && ver.y == ver1.y && ver1.x == ver.x) {
                    continue;
                }
                if (stug(hor1, ver1)) {
                    //cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
                    cout << "YES" << endl;
                    return;
                }
            }
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                cord hor1 = hor, ver1 = ver;
                hor1.y += dyhor[i];
                ver1.x += dxver[j];
                if (hor1.x == hor.x && hor1.y == hor.y && ver.y == ver1.y && ver1.x == ver.x) {
                    continue;
                }
                if (stug(hor1, ver1)) {
                    //cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
                    cout << "YES" << endl;
                    return;
                }
            }
            for (int j = 0; j < 3; ++j) {
                cord hor1 = hor, ver1 = ver;
                hor1.y += dyhor[i];
                ver1.y += dyver[j];
                if (hor1.x == hor.x && hor1.y == hor.y && ver.y == ver1.y && ver1.x == ver.x) {
                    continue;
                }
                if (stug(hor1, ver1)) {
                    //cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
                    cout << "YES" << endl;
                    return;
                }
            }
        }
    }
    cout << "NO" << endl;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27