Submission #1214689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214689		spetr	Toy (CEOI24_toy)	C++20	0 / 100	13 ms	3656 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>

ll pow(ll x, ll n, ll mod){
    if (n == 0){
        return 1;
    }
ll half = pow(x, n / 2, mod);
ll half_square = (half * half) % mod;

if (n % 2 == 0) {
    return half_square;
} else {
    return (half_square * x) % mod;
}
}   


ll inversion_x(ll x, ll m){
    ll vysledek = pow(x,m-2);
    return vysledek;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    
    ll w,h,k,l;
    cin >> w >> h >> k >> l;

    ll kx, ky, lx, ly;
    cin >> kx >> ky >> lx >> ly; //k-horiznot a l-vertikal
    vector<string> graf;
    for (ll i = 0; i < h; i++){
        string radek;
        cin >> radek;
        graf.push_back(radek);
    }

    vector<vector<bool>> visitedk, visitedl;
    vector<vector<bool>> fitl, fitk;
    for (ll i = 0; i < h; i++){
        vector<bool> radek;
        for (ll j = 0; j < w; j++){
            radek.push_back(false);
        }
        visitedk.push_back(radek);
        visitedl.push_back(radek);
        fitk.push_back(radek);
        fitl.push_back(radek);

    }

    // Kontrola, že se vejdou
    vll left, right, up, down;
    for (ll i = 0; i < h; i++){
        vl radek;
        for (ll j = 0; j < w; j++){
            radek.push_back(0);

        }
        left.push_back(radek);
        right.push_back(radek);
        up.push_back(radek);
        down.push_back(radek);

    }
   
    for (ll i = 0; i < w; i++){
        ll aktual1 = -1;
        ll aktual2 = h;
        for (ll j = 0; j < h; j++){
            if (graf[j][i] == 'X'){
                aktual1 = j;
            }
            down[j][i] = aktual1;

        }
        for (ll j = h-1; j >= 0; j--){
            if (graf[j][i] == 'X'){
                aktual2 = j;
            }
            up[j][i] = aktual2;

        }
    }
    
    for (ll i = 0; i < h; i++){
        ll aktual1 = -1;
        ll aktual2 = w;
        for (ll j = 0; j < w; j++){
            if (graf[i][j] == 'X'){
                aktual1 = j;
            }
            right[i][j] = aktual1;;

        }
        for (ll j = w-1; j >= 0; j--){
            if (graf[i][j] == 'X'){
                aktual2 = j;
            }
            left[i][j] = aktual2;;

        }
    }

    for(ll i = 0; i < h; i++){
        for(ll j = 0; j < w; j++){
            if (left[i][j] - right[i][j] > k){
                fitk[i][j] = true;
            }
        }
        for(ll j = 0; j < w; j++){
            if (up[i][j] - down[i][j]  > l){
                fitl[i][j] = true;
            }
        }
    }



    queue<vl> fronta; //y, x, horizont-k-0 / vertikal-l-1
    for (ll i = 0; i < k; i++){
        fronta.push({ky, kx + i, 0});
        visitedk[ky][kx+i] = true;
    }
    for (ll i = 0; i < l; i++){
        fronta.push({ly+i, lx, 1});
        visitedl[ly+i][lx] = true;
    }

    while (fronta.size() > 0){
        vl prvek = fronta.front();
        fronta.pop();
        if (graf[prvek[0]][prvek[1]] == '*'){
            if (fitl[prvek[0]][prvek[1]] == true && fitk[prvek[0]][prvek[1]] == true){
                cout << "YES";
                return 0;
            }
        }

        if (prvek[2] == 1){
            if (fitk[prvek[0]][prvek[1]] == true){
                if (visitedk[prvek[0]][prvek[1]] == false) {fronta.push({prvek[0],prvek[1], 0}); visitedk[prvek[0]][prvek[1]] = true;}
                for (ll i = 1; i < k; i++){
                    if (prvek[1] + i < w && graf[prvek[0]][prvek[1] + i] != 'X' && visitedk[prvek[0]][prvek[1] + i] == false){
                        visitedk[prvek[0]][prvek[1] + i] = true;
                        //visitedl[prvek[0]][prvek[1] + i] = true;
                        fronta.push({prvek[0],prvek[1] + i, 0});
                    }
                    else if (prvek[1] - i >= w || graf[prvek[0]][prvek[1]+i] == 'X'){
                        break;
                    }

                }
                for (ll i = 1; i < k; i++){
                    if (prvek[1] - i >= 0 && graf[prvek[0]][prvek[1] - i] != 'X' && visitedk[prvek[0]][prvek[1] - i] == false){
                        visitedk[prvek[0]][prvek[1] - i] = true;
                        //visitedl[prvek[0]][prvek[1] - i] = true;
                        fronta.push({prvek[0],prvek[1] - i, 0});
                    }
                    else if (prvek[1] - i < 0 || graf[prvek[0]][prvek[1]-i] == 'X'){
                        break;
                    }

                }
            }
        }
        else{
            if (fitl[prvek[0]][prvek[1]] == true){
                if (visitedl[prvek[0]][prvek[1]] == false) {fronta.push({prvek[0],prvek[1], 1}); visitedk[prvek[0]][prvek[1]] = true;}
                for (ll i = 1; i < l; i++){
                    if (prvek[0] + i < h && graf[prvek[0] + i][prvek[1]] != 'X' && visitedl[prvek[0] + i][prvek[1]] == false){
                        //visitedk[prvek[0]+i][prvek[1]] = true;
                        visitedl[prvek[0]+i][prvek[1]] = true;
                        fronta.push({prvek[0]+i,prvek[1], 1});
                    }
                    else if (prvek[0] + i >= h || graf[prvek[0] + i][prvek[1]] == 'X'){
                        break;
                    }
                    
                }
                for (ll i = 1; i < l; i++){
                    if (prvek[0] - i >= 0 && graf[prvek[0]-i][prvek[1]] != 'X' && visitedl[prvek[0]-i][prvek[1]] == false){
                        //visitedk[prvek[0]-i][prvek[1]] = true;
                        visitedl[prvek[0]-i][prvek[1]] = true;
                        fronta.push({prvek[0]-i,prvek[1], 1});
                    }
                    else if (prvek[0] - i < 0 || graf[prvek[0] - i][prvek[1]] == 'X'){
                        break;
                    }
                }
            }
        }
    }


    cout << "NO";
    return 0;
}

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