oj.uz

Submission #1045769

# Submission time Handle Problem Language Result Execution time Memory
1045769 2024-08-06T07:33:44 Z c2zi6 Toy (CEOI24_toy) C++14
14 / 100
 78 ms 11496 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef vector<bool> VB;
typedef vector<VB> VVB;
 
int n, m;
int K, L;

void replace(VVC& table, char a, char b) {
    rep(i, n) rep(j, m) if (table[i][j] == a) table[i][j] = b;
}

void expose(VVC& table, int sx, int sy) {
    VVB vis(n, VB(m));
    queue<PII> q;
    q.push({sx, sy});
    vis[sx][sy] = true;
    while (q.size()) {
        auto[ux, uy] = q.front();
        q.pop();
        VPI harevan;
        harevan.pb({ux-1, uy});
        harevan.pb({ux+1, uy});
        harevan.pb({ux, uy-1});
        harevan.pb({ux, uy+1});
        for (auto[vx, vy] : harevan) {
            if (vx < 0 || vx >= n || vy < 0 || vy >= m) continue;
            if (vis[vx][vy]) continue;
            if (table[vx][vy] == 'X') continue;
            q.push({vx, vy});
            vis[vx][vy] = true;
        }
    }
    rep(i, n) rep(j, m) if (vis[i][j]) table[i][j] = 'G';
    replace(table, '.', 'X');
    replace(table, 'G', '.');
}

const int MAXN = 50;
struct STATE {
    int ax, ay, bx, by;
    /*1 1, 1 0*/
    bool canbe() {
        /*ax is in range [bx, bx+L-1]*/
        /*ay is in range [by-K+1, by]*/
        bool p1 = (bx <= ax && ax <= bx+L-1);
        bool p2 = (by-K+1 <= ay && ay <= by);
        return p1 && p2;
    }
    int ind() {
        return 50*50*50*ax + 50*50*ay + 50*bx + by;
    }
    vector<STATE> harevan() {
        vector<STATE> ret;
        ret.pb({ax-1, ay, bx, by});
        ret.pb({ax+1, ay, bx, by});
        ret.pb({ax, ay-1, bx, by});
        ret.pb({ax, ay+1, bx, by});
        ret.pb({ax, ay, bx-1, by});
        ret.pb({ax, ay, bx+1, by});
        ret.pb({ax, ay, bx, by-1});
        ret.pb({ax, ay, bx, by+1});
        vector<STATE> ret2;
        for (STATE a : ret) {
            if (a.ax < 0 || a.ax >= n || a.bx < 0 || a.bx >= n) continue;
            if (a.ay < 0 || a.ay >= m || a.by < 0 || a.by >= m) continue;
            ret2.pb(a);
        }
        return ret2;
    }
};

void solve() {
    cin >> m >> n >> K >> L;
    // K - width, L - height
    int hx, hy, vx, vy;
    cin >> hy >> hx >> vy >> vx;
    VVC table, a, b;
    table = a = b = VVC(n, VC(m, 'X'));
    rep(i, n) rep(j, m) cin >> table[i][j];
    int destx, desty;
    rep(i, n) rep(j, m) {
        if (table[i][j] == '*') {
            destx = i;
            desty = j;
            table[i][j] = '.';
            break;
        }
    }
    rep(i, n) rep(j, m) {
        if (j+K-1 < m) {
            bool can = true;
            replr(c, j, j+K-1) {
                if (table[i][c] == 'X') can = false;
            }
            if (can) a[i][j] = '.';
        }
        if (i+L-1 < n) {
            bool can = true;
            replr(r, i, i+L-1) {
                if (table[r][j] == 'X') can = false;
            }
            if (can) b[i][j] = '.';
        }
    }
    expose(a, hx, hy);
    expose(b, vx, vy);
    /*cout << endl << "possible moves horizontal" << endl;*/
    /*rep(i, n) {*/
    /*    rep(j, m) cout << a[i][j];*/
    /*    cout << endl;*/
    /*}*/
    /*cout << endl << "possible moves vertical" << endl;*/
    /*rep(i, n) {*/
    /*    rep(j, m) cout << b[i][j];*/
    /*    cout << endl;*/
    /*}*/
    STATE start{hx, hy, vx, vy};
    queue<STATE> q;
    VB vis(50*50*50*50);
    q.push(start);
    vis[start.ind()] = true;

    vector<STATE> states;
    states.pb(start);

    while (q.size()) {
        STATE u = q.front();
        q.pop();
        for (STATE v : u.harevan()) {
            if (vis[v.ind()]) continue;
            if (a[v.ax][v.ay] == 'X') continue;
            if (b[v.bx][v.by] == 'X') continue;
            if (!v.canbe()) continue;
            vis[v.ind()] = true;
            q.push(v);
            states.pb(v);
        }
    }

    for (STATE s : states) {
        /*cout << "State (" << s.ay << ", " << s.ax << "), (" << s.by << ", " << s.bx << ")" << endl;*/
        bool p1 = (s.ax == destx && desty-K+1 <= s.ay && s.ay <= desty);
        bool p2 = (s.by == desty && destx-L+1 <= s.bx && s.bx <= destx);
        if (p1 && p2) {
            cout << "YES" << endl;
            return;
        }
        /*cout << "State (" << s.ax << ", " << s.ay << "), (" << s.bx << ", " << s.by << ")" << endl;*/
    }
    cout << "NO" << endl;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	/*freopen("mincross.in", "r", stdin); */
	/*freopen("test.out", "w", stdout); */
	int t = 1;
	/*cin >> t; */
	while (t--) solve();
}

Compilation message

Main.cpp: In function 'void expose(VVC&, int, int)':
Main.cpp:50:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |         auto[ux, uy] = q.front();
      |             ^
Main.cpp:57:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for (auto[vx, vy] : harevan) {
      |                  ^
Main.cpp: In function 'void solve()':
Main.cpp:112:9: warning: 'destx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |     int destx, desty;
      |         ^~~~~
Main.cpp:112:16: warning: 'desty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |     int destx, desty;
      |                ^~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1624 KB Output is correct
4 Correct 57 ms 11192 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 0 ms 1116 KB Output is correct
7 Correct 2 ms 1372 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 0 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 0 ms 1116 KB Output is correct
15 Correct 67 ms 10656 KB Output is correct
16 Correct 67 ms 9688 KB Output is correct
17 Correct 65 ms 9920 KB Output is correct
18 Correct 77 ms 11496 KB Output is correct
19 Correct 78 ms 9892 KB Output is correct
20 Correct 72 ms 11224 KB Output is correct
21 Correct 72 ms 10452 KB Output is correct
22 Correct 73 ms 10300 KB Output is correct
23 Correct 72 ms 10872 KB Output is correct
24 Correct 34 ms 7348 KB Output is correct
25 Correct 38 ms 5592 KB Output is correct
26 Correct 36 ms 6660 KB Output is correct
27 Correct 25 ms 7108 KB Output is correct
28 Correct 23 ms 3296 KB Output is correct
29 Correct 20 ms 3360 KB Output is correct
30 Correct 22 ms 3288 KB Output is correct
31 Correct 27 ms 7124 KB Output is correct
32 Correct 15 ms 2272 KB Output is correct
33 Correct 18 ms 3412 KB Output is correct
34 Correct 23 ms 3292 KB Output is correct
35 Correct 25 ms 3288 KB Output is correct
36 Correct 1 ms 1116 KB Output is correct
37 Correct 6 ms 2024 KB Output is correct
38 Correct 7 ms 2416 KB Output is correct
39 Correct 7 ms 1768 KB Output is correct
40 Correct 7 ms 1816 KB Output is correct
41 Correct 8 ms 2276 KB Output is correct
42 Correct 1 ms 1116 KB Output is correct
43 Correct 1 ms 1116 KB Output is correct
44 Correct 1 ms 1116 KB Output is correct
45 Correct 1 ms 1116 KB Output is correct
46 Correct 0 ms 1116 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1624 KB Output is correct
4 Correct 57 ms 11192 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 0 ms 1116 KB Output is correct
7 Correct 2 ms 1372 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 0 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 0 ms 1116 KB Output is correct
15 Correct 67 ms 10656 KB Output is correct
16 Correct 67 ms 9688 KB Output is correct
17 Correct 65 ms 9920 KB Output is correct
18 Correct 77 ms 11496 KB Output is correct
19 Correct 78 ms 9892 KB Output is correct
20 Correct 72 ms 11224 KB Output is correct
21 Correct 72 ms 10452 KB Output is correct
22 Correct 73 ms 10300 KB Output is correct
23 Correct 72 ms 10872 KB Output is correct
24 Correct 34 ms 7348 KB Output is correct
25 Correct 38 ms 5592 KB Output is correct
26 Correct 36 ms 6660 KB Output is correct
27 Correct 25 ms 7108 KB Output is correct
28 Correct 23 ms 3296 KB Output is correct
29 Correct 20 ms 3360 KB Output is correct
30 Correct 22 ms 3288 KB Output is correct
31 Correct 27 ms 7124 KB Output is correct
32 Correct 15 ms 2272 KB Output is correct
33 Correct 18 ms 3412 KB Output is correct
34 Correct 23 ms 3292 KB Output is correct
35 Correct 25 ms 3288 KB Output is correct
36 Correct 1 ms 1116 KB Output is correct
37 Correct 6 ms 2024 KB Output is correct
38 Correct 7 ms 2416 KB Output is correct
39 Correct 7 ms 1768 KB Output is correct
40 Correct 7 ms 1816 KB Output is correct
41 Correct 8 ms 2276 KB Output is correct
42 Correct 1 ms 1116 KB Output is correct
43 Correct 1 ms 1116 KB Output is correct
44 Correct 1 ms 1116 KB Output is correct
45 Correct 1 ms 1116 KB Output is correct
46 Correct 0 ms 1116 KB Output is correct
47 Correct 12 ms 2284 KB Output is correct
48 Runtime error 1 ms 2052 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 10 ms 2268 KB Output is correct
4 Runtime error 12 ms 2928 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1624 KB Output is correct
4 Correct 57 ms 11192 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 0 ms 1116 KB Output is correct
7 Correct 2 ms 1372 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 0 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 0 ms 1116 KB Output is correct
15 Correct 67 ms 10656 KB Output is correct
16 Correct 67 ms 9688 KB Output is correct
17 Correct 65 ms 9920 KB Output is correct
18 Correct 77 ms 11496 KB Output is correct
19 Correct 78 ms 9892 KB Output is correct
20 Correct 72 ms 11224 KB Output is correct
21 Correct 72 ms 10452 KB Output is correct
22 Correct 73 ms 10300 KB Output is correct
23 Correct 72 ms 10872 KB Output is correct
24 Correct 34 ms 7348 KB Output is correct
25 Correct 38 ms 5592 KB Output is correct
26 Correct 36 ms 6660 KB Output is correct
27 Correct 25 ms 7108 KB Output is correct
28 Correct 23 ms 3296 KB Output is correct
29 Correct 20 ms 3360 KB Output is correct
30 Correct 22 ms 3288 KB Output is correct
31 Correct 27 ms 7124 KB Output is correct
32 Correct 15 ms 2272 KB Output is correct
33 Correct 18 ms 3412 KB Output is correct
34 Correct 23 ms 3292 KB Output is correct
35 Correct 25 ms 3288 KB Output is correct
36 Correct 1 ms 1116 KB Output is correct
37 Correct 6 ms 2024 KB Output is correct
38 Correct 7 ms 2416 KB Output is correct
39 Correct 7 ms 1768 KB Output is correct
40 Correct 7 ms 1816 KB Output is correct
41 Correct 8 ms 2276 KB Output is correct
42 Correct 1 ms 1116 KB Output is correct
43 Correct 1 ms 1116 KB Output is correct
44 Correct 1 ms 1116 KB Output is correct
45 Correct 1 ms 1116 KB Output is correct
46 Correct 0 ms 1116 KB Output is correct
47 Correct 12 ms 2284 KB Output is correct
48 Runtime error 1 ms 2052 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1624 KB Output is correct
4 Correct 57 ms 11192 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 0 ms 1116 KB Output is correct
7 Correct 2 ms 1372 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 0 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 0 ms 1116 KB Output is correct
15 Correct 67 ms 10656 KB Output is correct
16 Correct 67 ms 9688 KB Output is correct
17 Correct 65 ms 9920 KB Output is correct
18 Correct 77 ms 11496 KB Output is correct
19 Correct 78 ms 9892 KB Output is correct
20 Correct 72 ms 11224 KB Output is correct
21 Correct 72 ms 10452 KB Output is correct
22 Correct 73 ms 10300 KB Output is correct
23 Correct 72 ms 10872 KB Output is correct
24 Correct 34 ms 7348 KB Output is correct
25 Correct 38 ms 5592 KB Output is correct
26 Correct 36 ms 6660 KB Output is correct
27 Correct 25 ms 7108 KB Output is correct
28 Correct 23 ms 3296 KB Output is correct
29 Correct 20 ms 3360 KB Output is correct
30 Correct 22 ms 3288 KB Output is correct
31 Correct 27 ms 7124 KB Output is correct
32 Correct 15 ms 2272 KB Output is correct
33 Correct 18 ms 3412 KB Output is correct
34 Correct 23 ms 3292 KB Output is correct
35 Correct 25 ms 3288 KB Output is correct
36 Correct 1 ms 1116 KB Output is correct
37 Correct 6 ms 2024 KB Output is correct
38 Correct 7 ms 2416 KB Output is correct
39 Correct 7 ms 1768 KB Output is correct
40 Correct 7 ms 1816 KB Output is correct
41 Correct 8 ms 2276 KB Output is correct
42 Correct 1 ms 1116 KB Output is correct
43 Correct 1 ms 1116 KB Output is correct
44 Correct 1 ms 1116 KB Output is correct
45 Correct 1 ms 1116 KB Output is correct
46 Correct 0 ms 1116 KB Output is correct
47 Correct 12 ms 2284 KB Output is correct
48 Runtime error 1 ms 2052 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -