oj.uz

Submission #1045739

# Submission time Handle Problem Language Result Execution time Memory
1045739 2024-08-06T07:19:05 Z CyberCow Toy (CEOI24_toy) C++17
0 / 100
 4 ms 14940 KB 
#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((x).size())
typedef long long ll;
using ull = unsigned long long;
using namespace std;
mt19937 rnd(348502);
ll mod1 = 998244353;
ll mod = 1e9 + 7;
const ll N = 1505;

int a[N][N];
int achdzax[N][N];
int verevnerqev[N][N];
int color[N][N];

void solve()
{
    int n, i, j, m, x, y, c, skx = -1, sky = -1, vrx = -1, vry = -1, k, l;
    cin >> m >> n >> k >> l;
    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;
    for ( i = 1; i <= n; i++)
    {
        for ( j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            if (c == '*')
            {
                vrx = i;
                vry = j;
            }
            else if(c == 'X')
            {
                a[i][j] = 1;
            }
        }
    }
    for ( i = 1; i <= n; i++)
    {
        int qan = 0;
        for ( j = 1; j <= m; j++)
        {
            if (a[i][j] == 1)
                qan = 0;
            else
                qan++;
            achdzax[i][j] += qan;
        }
        qan = 0;
        for ( j = m; j >= 1; j--)
        {
            if (a[i][j] == 1)
            {
                qan = 0;
            }
            else
            {
                qan++;
            }
            achdzax[i][j] += max(0, qan - 1);
        }
    }
    for ( j = 1; j <= m; j++)
    {
        int qan = 0;
        for ( i = 1; i <= n; i++)
        {
            if (a[i][j] == 1)
            {
                qan = 0;
            }
            else
            {
                qan++;
            }
            verevnerqev[i][j] += qan;
        }
        qan = 0;
        for (i = n; i >= 1; i--)
        {
            if (a[i][j] == 1)
            {
                qan = 0;
            }
            else
            {
                qan++;
            }
            verevnerqev[i][j] += max(0, qan - 1);
        }
    }
    for ( i = 0; i <= n + 1; i++)
    {
        a[i][0] = 1;
        a[i][m + 1] = 1;
    }
    for ( i = 0; i <= m + 1; i++)
    {
        a[0][i] = 1;
        a[n + 1][i] = 1;
    }
    queue<pair<int, int>> q;
    skx = yh;
    sky = xv;
    q.push({ skx + 1, sky + 1 });
    while (!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        color[x][y] = 1;
        q.pop();
        if (min(achdzax[x - 1][y], achdzax[x][y]) >= k && color[x - 1][y] == 0)
        {
            q.push({ x - 1, y });
            color[x - 1][y] = 1;
        }
        if (min(achdzax[x + 1][y], achdzax[x][y]) >= k && color[x + 1][y] == 0)
        {
            q.push({ x + 1, y });
            color[x + 1][y] = 1;
        }
        if (min(verevnerqev[x][y - 1], verevnerqev[x][y]) >= l && color[x][y - 1] == 0)
        {
            q.push({ x, y - 1 });
            color[x][y - 1] = 1;
        }
        if (min(verevnerqev[x][y + 1], verevnerqev[x][y]) >= l && color[x][y + 1] == 0)
        {
            q.push({ x, y + 1 });
            color[x][y + 1] = 1;
        }
    }
    if (color[vrx][vry] == 1)
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:38:27: warning: unused variable 'c' [-Wunused-variable]
   38 |     int n, i, j, m, x, y, c, skx = -1, sky = -1, vrx = -1, vry = -1, k, l;
      |                           ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6612 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6612 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 10724 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 6608 KB Output is correct
13 Correct 1 ms 10588 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct
16 Correct 1 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 1 ms 7004 KB Output is correct
19 Correct 1 ms 7004 KB Output is correct
20 Correct 1 ms 7004 KB Output is correct
21 Correct 1 ms 4956 KB Output is correct
22 Correct 1 ms 4956 KB Output is correct
23 Correct 1 ms 4956 KB Output is correct
24 Correct 1 ms 6748 KB Output is correct
25 Correct 1 ms 6748 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Correct 1 ms 6748 KB Output is correct
28 Correct 1 ms 6748 KB Output is correct
29 Correct 1 ms 6748 KB Output is correct
30 Correct 1 ms 6748 KB Output is correct
31 Correct 1 ms 6748 KB Output is correct
32 Correct 1 ms 6608 KB Output is correct
33 Correct 1 ms 6748 KB Output is correct
34 Correct 1 ms 6748 KB Output is correct
35 Correct 1 ms 6612 KB Output is correct
36 Correct 1 ms 8540 KB Output is correct
37 Incorrect 1 ms 6748 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6612 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 10724 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 6608 KB Output is correct
13 Correct 1 ms 10588 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct
16 Correct 1 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 1 ms 7004 KB Output is correct
19 Correct 1 ms 7004 KB Output is correct
20 Correct 1 ms 7004 KB Output is correct
21 Correct 1 ms 4956 KB Output is correct
22 Correct 1 ms 4956 KB Output is correct
23 Correct 1 ms 4956 KB Output is correct
24 Correct 1 ms 6748 KB Output is correct
25 Correct 1 ms 6748 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Correct 1 ms 6748 KB Output is correct
28 Correct 1 ms 6748 KB Output is correct
29 Correct 1 ms 6748 KB Output is correct
30 Correct 1 ms 6748 KB Output is correct
31 Correct 1 ms 6748 KB Output is correct
32 Correct 1 ms 6608 KB Output is correct
33 Correct 1 ms 6748 KB Output is correct
34 Correct 1 ms 6748 KB Output is correct
35 Correct 1 ms 6612 KB Output is correct
36 Correct 1 ms 8540 KB Output is correct
37 Incorrect 1 ms 6748 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6612 KB Output is correct
3 Correct 1 ms 6744 KB Output is correct
4 Correct 3 ms 14908 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 3 ms 14936 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 4 ms 14684 KB Output is correct
14 Correct 4 ms 14936 KB Output is correct
15 Correct 3 ms 14312 KB Output is correct
16 Correct 2 ms 13228 KB Output is correct
17 Correct 3 ms 13100 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 3 ms 12516 KB Output is correct
20 Correct 3 ms 12380 KB Output is correct
21 Correct 3 ms 11868 KB Output is correct
22 Correct 3 ms 11868 KB Output is correct
23 Correct 3 ms 11792 KB Output is correct
24 Correct 3 ms 14312 KB Output is correct
25 Correct 4 ms 14396 KB Output is correct
26 Correct 3 ms 14428 KB Output is correct
27 Correct 3 ms 14428 KB Output is correct
28 Correct 3 ms 14428 KB Output is correct
29 Correct 3 ms 14428 KB Output is correct
30 Correct 4 ms 13404 KB Output is correct
31 Correct 3 ms 12328 KB Output is correct
32 Correct 3 ms 12380 KB Output is correct
33 Correct 3 ms 12380 KB Output is correct
34 Correct 3 ms 14172 KB Output is correct
35 Correct 3 ms 12328 KB Output is correct
36 Correct 2 ms 14684 KB Output is correct
37 Incorrect 3 ms 14132 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6612 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 10724 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 6608 KB Output is correct
13 Correct 1 ms 10588 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct
16 Correct 1 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 1 ms 7004 KB Output is correct
19 Correct 1 ms 7004 KB Output is correct
20 Correct 1 ms 7004 KB Output is correct
21 Correct 1 ms 4956 KB Output is correct
22 Correct 1 ms 4956 KB Output is correct
23 Correct 1 ms 4956 KB Output is correct
24 Correct 1 ms 6748 KB Output is correct
25 Correct 1 ms 6748 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Correct 1 ms 6748 KB Output is correct
28 Correct 1 ms 6748 KB Output is correct
29 Correct 1 ms 6748 KB Output is correct
30 Correct 1 ms 6748 KB Output is correct
31 Correct 1 ms 6748 KB Output is correct
32 Correct 1 ms 6608 KB Output is correct
33 Correct 1 ms 6748 KB Output is correct
34 Correct 1 ms 6748 KB Output is correct
35 Correct 1 ms 6612 KB Output is correct
36 Correct 1 ms 8540 KB Output is correct
37 Incorrect 1 ms 6748 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6612 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 10724 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 6608 KB Output is correct
13 Correct 1 ms 10588 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct
16 Correct 1 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 1 ms 7004 KB Output is correct
19 Correct 1 ms 7004 KB Output is correct
20 Correct 1 ms 7004 KB Output is correct
21 Correct 1 ms 4956 KB Output is correct
22 Correct 1 ms 4956 KB Output is correct
23 Correct 1 ms 4956 KB Output is correct
24 Correct 1 ms 6748 KB Output is correct
25 Correct 1 ms 6748 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Correct 1 ms 6748 KB Output is correct
28 Correct 1 ms 6748 KB Output is correct
29 Correct 1 ms 6748 KB Output is correct
30 Correct 1 ms 6748 KB Output is correct
31 Correct 1 ms 6748 KB Output is correct
32 Correct 1 ms 6608 KB Output is correct
33 Correct 1 ms 6748 KB Output is correct
34 Correct 1 ms 6748 KB Output is correct
35 Correct 1 ms 6612 KB Output is correct
36 Correct 1 ms 8540 KB Output is correct
37 Incorrect 1 ms 6748 KB Output isn't correct
38 Halted 0 ms 0 KB -