Submission #1125337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125337		cpptowin	Toy (CEOI24_toy)	C++20	100 / 100	206 ms	44800 KiB

Main

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1510
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if(x < 0) x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if(x < 0) x += mod;
}
int n,m,k,ll;
int a[N][N];
bool vis[N][N];
pii s,t,f;
int lrow[N][N],rrow[N][N],rcol[N][N],lcol[N][N];
bool save(int i,int j)
{
    return i and j and i <= n and j <= m and !a[i][j];
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> m >> n >> k >> ll;
    cin >> t.se >> t.fi >> s.se >> s.fi;
    t.fi++,t.se++,s.fi++,s.se++;
    fo(i,1,n) fo(j,1,m)
    {
        char t;
        cin >> t;
        if(t == 'X') a[i][j] = 1;
        if(t == '*') f = {i,j};
    }
    fo(i,1,n)
    {
        fo(j,1,m)
        {
            lrow[i][j] = lrow[i][j - 1];
            if(a[i][j]) lrow[i][j] = j;
        }
        rrow[i][m + 1] = m + 1;
        fod(j,m,1)
        {
            rrow[i][j] = rrow[i][j + 1];
            if(a[i][j]) rrow[i][j] = j;
        }
    }
    fo(j,1,m)
    {
        fo(i,1,n)
        {
            lcol[i][j] = lcol[i - 1][j];
            if(a[i][j]) lcol[i][j] = i;
        }
        rcol[n + 1][j] = n + 1;
        fod(i,n,1)
        {
            rcol[i][j] = rcol[i + 1][j];
            if(a[i][j]) rcol[i][j] = i;
        }
    }
    queue<pii> q;
    q.push({t.fi,s.se});
    vis[t.fi][s.se] = 1;
    while(ss(q))
    {
        auto [i,j] = q.front();
        q.pop();
//        cout << i << ' ' << j;
//        en;
        fo(x,0,1)
        {
            int i1 = i + (x == 0 ? 1 : -1);
            if(save(i1,j))
            {
                int l = max(lrow[i][j],lrow[i1][j]);
                int r = min(rrow[i][j],rrow[i1][j]);
//                cout << i1 << ' ' << j << ' ' << l << ' ' << r;en;
                if(r - l - 1 >= k)
                {
                    if(!vis[i1][j])
                    {
                        vis[i1][j] = 1;
                        q.push({i1,j});
                    }
                }
            }
            int j1 = j + (x == 0 ? 1 : -1);
            if(save(i,j1))
            {
                int l = max(lcol[i][j],lcol[i][j1]);
                int r = min(rcol[i][j],rcol[i][j1]);
//            if(i == 6 and j == 5)
//            {
//                cout << i << 'x' << j1 << ' ' <<l << ' ' << r <<  "xxx\n";
//            }
                if(r - l - 1 >= ll)
                {
                    if(!vis[i][j1])
                    {
                        vis[i][j1] = 1;
                        q.push({i,j1});
                    }
                }
            }
        }
    }
    if(vis[f.fi][f.se]) cout << "YES";
    else cout << "NO";
}

Compilation message (stderr)

Main.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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