Submission #1171925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171925		SmuggingSpun	Toy (CEOI24_toy)	C++20	100 / 100	294 ms	64080 KiB

Main

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
const int lim = 1505;
int H, n, m, V, xh, yh, xv, yv, x_target, y_target, f[lim][lim];
int get(int x, int y, int u, int v){
    return f[u][v] - (x == 0 ? 0 : f[x - 1][v]) - (y == 0 ? 0 : f[u][y - 1]) + (x == 0 || y == 0 ? 0 : f[x - 1][y - 1]);
}
char a[lim][lim];
namespace sub12{
    const int lim = 90;
    bitset<lim>vis[lim][lim][lim];
    queue<tuple<int, int, int, int>>q;
    bool inside(int i, int l, int r){
        return l <= i && r >= i;
    }
    void work(int xh, int yh, int xv, int yv){
        if(xh < 0 || xh >= n || yh < 0 || yh + H > m || xv < 0 || xv + V > n || yv < 0 || yv >=  m || get(xh, yh, xh, yh + H - 1) > 0 || get(xv, yv, xv + V - 1, yv) > 0 || vis[xh][yh][xv].test(yv) || !inside(yv, yh, yh + H - 1) || !inside(xh, xv, xv + V - 1)){
            return;
        }
        if(xh == x_target && yv == y_target){
            cout << "YES";
            exit(0);
        }
        q.emplace(xh, yh, xv, yv);
        vis[xh][yh][xv].set(yv);
    }
    void solve(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                for(int k = 0; k < n; k++){
                    vis[i][j][k].reset();
                }
            }
        }
        work(xh, yh, xv, yv);
        while(!q.empty()){
            tie(xh, yh, xv, yv) = q.front();
            q.pop();
            work(xh - 1, yh, xv, yv);
            work(xh + 1, yh, xv, yv);
            work(xh, yh - 1, xv, yv);
            work(xh, yh + 1, xv, yv);
            work(xh, yh, xv - 1, yv);
            work(xh, yh, xv + 1, yv);
            work(xh, yh, xv, yv - 1);
            work(xh, yh, xv, yv + 1);
        }
        cout << "NO";
    }
}
namespace sub345{
    int left[lim][lim], right[lim][lim], up[lim][lim], down[lim][lim], hor[lim][lim], ver[lim][lim];
    bitset<lim>vis[lim];
    void solve(){
        for(int i = 0; i < n; vis[i++].reset()){
            left[i][0] = (a[i][0] == 'X' ? 0 : -1);
            hor[i][0] = int(get(i, 0, i, H - 1) == 0);
            for(int j = 1; j < m; j++){
                left[i][j] = (a[i][j] == 'X' ? j : left[i][j - 1]);
                if(j + H <= m){
                    hor[i][j] = hor[i][j - 1] + int(get(i, j, i, j + H - 1) == 0);
                }
            }
            right[i][m - 1] = (a[i][m - 1] == 'X' ? m - 1 : m);
            for(int j = m - 2; j > -1; j--){
                right[i][j] = (a[i][j] == 'X' ? j : right[i][j + 1]);
            }
        }
        for(int j = 0; j < m; j++){
            up[0][j] = (a[0][j] == 'X' ? 0 : -1);
            ver[0][j] = int(get(0, j, V - 1, j) == 0);
            for(int i = 1; i < n; i++){
                up[i][j] = (a[i][j] == 'X' ? i : up[i - 1][j]);
                if(i + V <= n){
                    ver[i][j] = ver[i - 1][j] + int(get(i, j, i + V - 1, j) == 0);
                }
            }
            down[n - 1][j] = (a[n - 1][j] == 'X' ? n - 1 : n);
            for(int i = n - 2; i > -1; i--){
                down[i][j] = (a[i][j] == 'X' ? i : down[i + 1][j]);
            }
        }
        vis[xh].set(yv);
        queue<pair<int, int>>q;
        q.emplace(xh, yv);
        while(!q.empty()){
            auto [x, y] = q.front();
            q.pop();
            if(x == x_target && y == y_target){
                return void(cout << "YES");
            }
            int lh = max(y - H, left[x][y]) + 1, rh = min(y + H, right[x][y]) - H, uv = max(x - V, up[x][y]) + 1, dv = min(x + V, down[x][y]) - V;
            if(x > 0 && !vis[x - 1].test(y) && hor[x - 1][rh] > (lh == 0 ? 0 : hor[x - 1][lh - 1]) && uv < x){
                q.emplace(x - 1, y);
                vis[x - 1].set(y);
            }
            if(x + 1 < n && !vis[x + 1].test(y) && hor[x + 1][rh] > (lh == 0 ? 0 : hor[x + 1][lh - 1]) && dv > x - V + 1){
                q.emplace(x + 1, y);
                vis[x + 1].set(y);
            }
            if(y > 0 && !vis[x].test(y - 1) && ver[dv][y - 1] > (uv == 0 ? 0 : ver[uv - 1][y - 1]) && lh < y){
                q.emplace(x, y - 1);
                vis[x].set(y - 1);
            }
            if(y + 1 < m && !vis[x].test(y + 1) && ver[dv][y + 1] > (uv == 0 ? 0 : ver[uv - 1][y + 1]) && rh > y - H + 1){
                q.emplace(x, y + 1);
                vis[x].set(y + 1);
            }
        }
        cout << "NO";
    }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
    cin >> m >> n >> H >> V >> yh >> xh >> yv >> xv;
    memset(f, 0, sizeof(f));
    for(int i = 0; i < n; i++){
        for(int j = 0, sum = 0; j < m; j++){
            cin >> a[i][j];
            if(a[i][j] == 'X'){
                sum++;
            }
            f[i][j] = sum + (i == 0 ? 0 : f[i - 1][j]); 
            if(a[i][j] == '*'){
                x_target = i;
                y_target = j;
            }
        }
    }
    if(max(n, m) <= 90){
        sub12::solve();
    }
    else{
        sub345::solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:117:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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