Submission #1045615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045615		SamAnd	Toy (CEOI24_toy)	C++17	100 / 100	57 ms	42448 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 1503;

int n, m, k, l_;
int sx, sy, fx, fy;
char a[N][N];

int u[N][N], d[N][N], l[N][N], r[N][N];
bool c[N][N];

pair<int, int> hat(int l, int r, int l2, int r2)
{
    return m_p(max(l, l2), min(r, r2));
}

void solv()
{
    cin >> m >> n >> k >> l_;
    cin >> u[0][0] >> sx >> sy >> u[0][0];
    ++sx;
    ++sy;
    assert(k <= m);
    assert(l_ <= n);
    for (int i = 1; i <= n; ++i)
        cin >> (a[i] + 1);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] == '*')
            {
                a[i][j] = '.';
                fx = i;
                fy = j;
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        l[i][0] = 1;
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] == 'X')
            {
                l[i][j] = j + 1;
            }
            else
            {
                l[i][j] = l[i][j - 1];
            }
        }
        r[i][m + 1] = m;
        for (int j = m; j >= 1; --j)
        {
            if (a[i][j] == 'X')
            {
                r[i][j] = j - 1;
            }
            else
            {
                r[i][j] = r[i][j + 1];
            }
        }
    }
    for (int j = 1; j <= m; ++j)
    {
        u[0][j] = 1;
        for (int i = 1; i <= n; ++i)
        {
            if (a[i][j] == 'X')
            {
                u[i][j] = i + 1;
            }
            else
            {
                u[i][j] = u[i - 1][j];
            }
        }
        d[n + 1][j] = n;
        for (int i = n; i >= 1; --i)
        {
            if (a[i][j] == 'X')
            {
                d[i][j] = i - 1;
            }
            else
            {
                d[i][j] = d[i + 1][j];
            }
        }
    }

    queue<pair<int, int> > q;
    c[sx][sy] = true;
    q.push(m_p(sx, sy));
    while (!q.empty())
    {
        int x = q.front().fi;
        int y = q.front().se;
        q.pop();

        pair<int, int> t = hat(l[x][y], r[x][y], l[x + 1][y], r[x + 1][y]);
        if (t.se - t.fi + 1 >= k)
        {
            int hx = x + 1;
            int hy = y;
            if (!c[hx][hy])
            {
                c[hx][hy] = true;
                q.push(m_p(hx, hy));
            }
        }
        t = hat(l[x][y], r[x][y], l[x - 1][y], r[x - 1][y]);
        if (t.se - t.fi + 1 >= k)
        {
            int hx = x - 1;
            int hy = y;
            if (!c[hx][hy])
            {
                c[hx][hy] = true;
                q.push(m_p(hx, hy));
            }
        }
        t = hat(u[x][y], d[x][y], u[x][y + 1], d[x][y + 1]);
        if (t.se - t.fi + 1 >= l_)
        {
            int hx = x;
            int hy = y + 1;
            if (!c[hx][hy])
            {
                c[hx][hy] = true;
                q.push(m_p(hx, hy));
            }
        }
        t = hat(u[x][y], d[x][y], u[x][y - 1], d[x][y - 1]);
        if (t.se - t.fi + 1 >= l_)
        {
            int hx = x;
            int hy = y - 1;
            if (!c[hx][hy])
            {
                c[hx][hy] = true;
                q.push(m_p(hx, hy));
            }
        }
    }

    if (c[fx][fy])
        cout << "YES\n";
    else
        cout << "NO\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

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