Submission #1140586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140586		hynmj	Toy (CEOI24_toy)	C++20	0 / 100	6 ms	6216 KiB

Main

//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define Code ios_base::sync_with_stdio(0);
#define by cin.tie(NULL);
#define Hayan cout.tie(NULL);
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define vb vector<bool>
#define vv vector<vi>
#define vp vector<pi>
#define ul map<int,vi>
#define ub map<int,bool>
#define ui map<int,int>
#define sum(a) accumulate(all(a),0)
#define add insert
#define endl '\n' 
#define pi pair<int,int>
#define ff first
#define ss second
#define ret(x) {cout <<x;return; }
using namespace std;
ul graph;
const int N = 1.52e3;
int u,v,n,k,m,e,w,h;
int vis[N][N];
char a[N][N];
bool valid(int i,int j)
{
    return (0 <= i && i < n) && (0 <= j && j < m); 
}
const vector<pi> nxt={{-1,0},{+1,0},{0,+1},{0,-1}};
bool TargetReached; 
bool WorkingOnVertical;
void dfs(int i, int j)
{
    // cout <<"starting in "<<i<< " "<< j<< endl;
    if (vis[i][j]==1)
    {

        // cout <<"already visited "<<i<< " "<< j<< endl;
        return;
    }
    vis[i][j]=1;
//     rep(n)
//     {
//         rep(j,m)
//         {
//             cout <<a[i][j];
//             cout <<' ';

//         }ln;
//     }ln;
    if (a[i][j] == 'X')
    {

        // cout <<"oops "<< i<< " "<<j<<" is not valid due to X " <<i << " "<<j<<endl;
        return;
    }   
    bool ok=0;
    // cout <<"these are being checked in "<< i << " "<<j <<endl;
    if (WorkingOnVertical)
        for (int ii= i; ii < i + v; ii++)
        {

            if (!valid(ii,j))
            {
                return;
                // cout <<"oops "<< i<< " "<<j<<" is not valid due to " <<ii << " "<<j<<endl;
            }
            if (a[ii][j]=='X')
            {
            // cout <<"oops "<< i<< " "<<j<<" is not valid due to X " <<ii << " "<<j<< " and also "<<a[ii][j] <<endl;
                return;
            }
            if (a[ii][j]=='*')
            {
            // cout <<"found "<< i<< " "<<j<<" is not valid due to X " <<ii << " "<<j<< " and also "<<a[ii][j] <<endl;
                ok=1;
            }
        // cout << ii<< " "<<j<<" ";
            // ln;
        // cout <<"this is somthing i wanna show "<< a[ii][j];ln;
        // cout <<" " <<ok<<endl;

        }
    else 
    {
        for (int jj= j; jj < j + h; jj++)
        {

            if (!valid(i,jj))
            {
                // cout <<"oops "<< i<< " "<<j<<" is not valid due to " <<i << " "<<jj<<endl;
                return;
            }
            if (
                a[i][jj]=='X')
            {
            // cout <<"oops "<< i<< " "<<j<<" is not valid due to X " <<i << " "<<jj<< " and also "<<a[i][jj] <<endl;
                return;
            }
            if (a[i][jj]=='*')
            {
                ok=1;
            }
        }
    }
    // if (WorkingOnVertical)cout <<i<<" :: " << j <<" "<<a[i][j]<<endl;
    if (ok)
    {
        TargetReached=1;
    // if (WorkingOnVertical)cout <<i<<" :: " << j <<" "<<a[i][j]<<endl;
        return;
    }
    for (auto inst:nxt )
    {
    // if (WorkingOnVertical)
    // cout <<"in the loop of "<<i<< ' '<<j<<' ';
        if (valid(i+inst.ff,j+inst.ss))
        {
            // cout <<"this is valid"<<endl;   
            // cout << i+inst.ff<< " "<<j+inst.ss<<endl;
            dfs(i+inst.ff,j+inst.ss);
        }
//         else 
//         {

//             cout <<"this is not valid"<<endl;   
//         cout << i+inst.ff<< " "<<j+inst.ss<<endl;
//         cout <<i+inst.ff<<" ::: " << j<<endl;
//         }
        if (TargetReached)return;
    }
}
void initiate()
{
    rep(n)
    {
        rep(j,m)
        {
            vis[i][j]=0;
        }
    }
}
void solve()
{
    int init_H_i ,init_H_j;
    int init_V_i ,init_V_j;

    cin >> m >> n;
    cin >> h >> v;
    cin>> init_V_j >> init_V_i; 
    cin>> init_H_j >> init_H_i; 
    rep(n)
    {
        rep(j,m)
        {
            cin>>a[i][j];
            // cout <<a[i][j]<<" ";
        }
        // ln;
    }
    initiate();
    WorkingOnVertical=0;

    TargetReached=0;
    // cout <<v<<" "<<h<<endl;
    dfs(init_V_i,init_V_j);
    if (!TargetReached)
        ret("NO")
    
    TargetReached=0;
    initiate();
    WorkingOnVertical=1;
    dfs(init_H_i,init_H_j);
    
    if (!TargetReached)
        ret("NO")
    ret("YES")


    // for (auto i: a){cout<<i<<" ";}
}
signed main(){
    Code by Hayan
    int ans=1;
    TargetReached=0;
    //cout<<setprecision(1000);
    // cin>>ans;
    while(ans--){
        // cout << "Case #" << ans << ": \n";
        solve();ln;}}

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