Submission #1233554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233554		sophiaeternalia	Toy (CEOI24_toy)	C++20	0 / 100	1 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

    int w, h, k, l, xh, yh, xv, yv, x, y;
    cin>>w>>h>>k>>l>>xh>>yh>>xv>>yv;
    y=xv;
    x=yh;
    vector<string> tt(h);
    for (int i=0; i<h; i++){
        cin>>tt[i];
    }
    vector<vector<array<int, 4>>> t(h, vector<array<int, 4>> (w, {-1, w, -1, h}));
    for (int i=0; i<h; i++){
        int a=-1;
        for (int j=0; j<w; j++){
            if (tt[i][j]=='X'){
                //cout<<"a "<<j<<"\n";
                a=j;
            } else {
                t[i][j][0]=a;
            }
        }
        a=w;
        for (int j=w-1; j>=0; j--){
            if (tt[i][j]=='X'){
                //cout<<"b "<<j<<"\n";
                a=j;
            } else {
                t[i][j][1]=a;
            }
        }
    }
    for (int i=0; i<w; i++){
        int a=-1;
        for (int j=0; j<h; j++){
            if (tt[j][i]=='X'){
                //cout<<"c "<<j<<"\n";
                a=j;
            } else {
                t[j][i][2]=a;
            }
        }
        a=h;
        for (int j=h-1; j>=0; j--){
            if (tt[j][i]=='X'){
                //cout<<"d "<<j<<"\n";
                a=j;
            } else {
                t[j][i][3]=a;
            }
        }
    }
    /*for (auto u: t){
        for (auto v: u){
            for (auto w: v){
                cout<<w<<"_";
            }
            cout<<"    ";
        }
        cout<<"\n";
    }*/
    vector<vector<int>> vi(h, vector<int> (w, 0));
    queue<pair<int, int>> q;
    swap(x, y);
    q.push({x, y});
    while (!q.empty()){
        x=q.front().first;
        y=q.front().second;
        //cout<<x<<" "<<y<<"\n";
        q.pop();
        if (vi[x][y]==1){
            continue;
        }
        vi[x][y]=1;
        if (tt[x][y]=='*'){
            cout<<"YES"<<"\n";
            return 0;
        }
        if (t[x][y][0]!=y-1){
            if (min(t[x][y-1][1], t[x][y][1])-max(t[x][y-1][0], t[x][y][0])-1>=k){
                //cout<<'a'<<" "<<x<<" "<<y-1<<"\n";
                q.push({x, y-1});
            }
        }
        if (t[x][y][1]!=y+1){
            if (min(t[x][y+1][1], t[x][y][1])-max(t[x][y+1][0], t[x][y][0])-1>=k){
                //cout<<'b'<<" "<<x<<" "<<y+1<<"\n";
                q.push({x, y+1});
            }
        }
        if (t[x][y][2]!=x-1){
            if (min(t[x-1][y][3], t[x][y][3])-max(t[x-1][y][2], t[x][y][2])-1>=l){
                //cout<<'c'<<" "<<x-1<<" "<<y<<"\n";
                q.push({x-1, y});
            }
        }
        if (t[x][y][2]!=x+1){
            if (min(t[x+1][y][3], t[x][y][3])-max(t[x+1][y][2], t[x][y][2])-1>=l){
                //cout<<'d'<<" "<<x+1<<" "<<y<<"\n";
                q.push({x+1, y});
            }
        }
    }
    cout<<"NO"<<"\n";
}

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