oj.uz

Submission #1045912

# Submission time Handle Problem Language Result Execution time Memory
1045912 2024-08-06T08:29:29 Z VahanAbraham Toy (CEOI24_toy) C++17
14 / 100
 1500 ms 46164 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <bitset>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <cassert>
 
using namespace std;
 
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout);
 
ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}
 
const int N = 400;
const ll oo = 100000000000000000, MOD = 1000000007;
 
struct cord {
    int x, y;
};
 
char grid[N][N];
bool normalahor[N][N], normalaver[N][N];
int w, h, k, l, xend, yend;
map <pair<int, pair<int, pair<int, int>>>, bool> ok;
 
int dxhor[3] = { 1,-1,0 };
int dxver[3] = { 1,-1,0 };
int dyhor[3] = { 1,-1,0 };
int dyver[3] = { 1,-1,0 };
 
queue<pair<cord, cord>> q;
 
pair<int, int> hatvumen(cord hor, cord ver) {
    for (int i = ver.x; i <= ver.x; ++i) {
        if (hor.y >= ver.y && hor.y <= ver.y + l - 1 && i >=hor.x && i<=hor.x+k-1) {
            return { i,hor.y };
        }
    }
    return{ -1,-1 };
}
 
bool mejnahor(cord hor) {
    if (hor.x >= 0 && hor.x + k - 1 <= w - 1 && hor.y >= 0 && hor.y <= h - 1) {
        return true;
    }
    return false;
}
 
bool mejnaver(cord ver) {
    if (ver.x >= 0 && ver.x <= w - 1 && ver.y >= 0 && ver.y+l-1 <= h - 1) {
        return true;
    }
    return false;
}
 
bool normalhor(cord hor) {
    for (int i = hor.x; i <= hor.x + k - 1; ++i) {
        if (grid[hor.y][i] == 'X') {
            return false;
        }
    }
    return true;
}
 
bool normalver(cord ver) {
    for (int i = ver.y; i <= ver.y + l - 1; ++i) {
        if (grid[i][ver.x] == 'X') {
            return false;
        }
    }
    return true;
}
 
bool stug(cord hor1, cord ver1) {
    if (mejnahor(hor1) == 1 && mejnaver(ver1) == 1 && normalahor[hor1.x][hor1.y] == 1 && normalaver[ver1.x][ver1.y] == 1) {
        pair<int, int> p = hatvumen(hor1, ver1);
        if (p.fr == xend && p.sc == yend){
            return true;
        }
        else {
            if (p.fr != -1) {
                if (ok[{hor1.x, { hor1.y,{ver1.x,ver1.y} }}] != 1) {
                    ok[{hor1.x, { hor1.y,{ver1.x,ver1.y} }}] = 1;
                    q.push({ hor1,ver1 });
                    return false;
                }
                return false;
            }
            return false;
        }
        return false;
    }
    return false;
}
 
 
void solve() {
    cin >> w >> h >> k >> l;
    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;
    cord hor, ver;
    hor.x = xh;
    hor.y = yh;
    ver.x = xv;
    ver.y = yv;
    ok[{hor.x, { hor.y,{ver.x,ver.y} }}] = 1;
    q.push({ hor,ver });
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == '*') {
                xend = j, yend = i;
            }
        }
    }
    /*cout << xend << " " << yend << endl;
    cord vv;
    vv.x = 1, vv.y = 0;
    cout << normalver(vv) << endl;*/
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cord yy;
            yy.x = j, yy.y = i;
            if (mejnaver(yy)) {
                normalaver[j][i] = normalver(yy);
            }
            if (mejnahor(yy)) {
                normalahor[j][i] = normalhor(yy);
            }
        }
    }
    while (q.empty() != 1) {
        hor = q.front().fr;
        ver = q.front().sc;
        //cout << hor.x << " " << hor.y << " " << ver.x << " " << ver.y << endl;
        q.pop();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                cord hor1 = hor, ver1 = ver;
                hor1.x += dxhor[i];
                ver1.x += dxver[j];
                if (stug(hor1, ver1)) {
                    //cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
                    cout << "YES" << endl;
                    return;
                }
            }
            for (int j = 0; j < 3; ++j) {
                cord hor1 = hor, ver1 = ver;
                hor1.x += dxhor[i];
                ver1.y += dyver[j];
                if (stug(hor1, ver1)) {
                    //cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
                    cout << "YES" << endl;
                    return;
                }
            }
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                cord hor1 = hor, ver1 = ver;
                hor1.y += dyhor[i];
                ver1.x += dxver[j];
                if (stug(hor1, ver1)) {
                    //cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
                    cout << "YES" << endl;
                    return;
                }
            }
            for (int j = 0; j < 3; ++j) {
                cord hor1 = hor, ver1 = ver;
                hor1.y += dyhor[i];
                ver1.y += dyver[j];
                if (stug(hor1, ver1)) {
                    //cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
                    cout << "YES" << endl;
                    return;
                }
            }
        }
    }
    cout << "NO" << endl;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Subtask #0
0.0 / 0.0

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 7 ms 800 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 9 ms 860 KB Output is correct
8 Correct 0 ms 412 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 853 ms 23888 KB Output is correct
16 Correct 732 ms 20280 KB Output is correct
17 Correct 811 ms 22056 KB Output is correct
18 Correct 948 ms 26960 KB Output is correct
19 Correct 955 ms 26788 KB Output is correct
20 Correct 942 ms 26448 KB Output is correct
21 Correct 967 ms 26792 KB Output is correct
22 Correct 933 ms 26568 KB Output is correct
23 Correct 968 ms 26356 KB Output is correct
24 Correct 393 ms 11932 KB Output is correct
25 Correct 343 ms 10788 KB Output is correct
26 Correct 302 ms 9236 KB Output is correct
27 Correct 263 ms 8604 KB Output is correct
28 Correct 236 ms 7760 KB Output is correct
29 Correct 204 ms 6996 KB Output is correct
30 Correct 65 ms 2744 KB Output is correct
31 Correct 274 ms 8960 KB Output is correct
32 Correct 44 ms 2132 KB Output is correct
33 Correct 129 ms 4948 KB Output is correct
34 Correct 109 ms 4176 KB Output is correct
35 Correct 115 ms 4436 KB Output is correct
36 Correct 3 ms 604 KB Output is correct
37 Correct 56 ms 2188 KB Output is correct
38 Correct 61 ms 2580 KB Output is correct
39 Correct 62 ms 2336 KB Output is correct
40 Correct 58 ms 2388 KB Output is correct
41 Correct 65 ms 2640 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 7 ms 800 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 9 ms 860 KB Output is correct
8 Correct 0 ms 412 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 853 ms 23888 KB Output is correct
16 Correct 732 ms 20280 KB Output is correct
17 Correct 811 ms 22056 KB Output is correct
18 Correct 948 ms 26960 KB Output is correct
19 Correct 955 ms 26788 KB Output is correct
20 Correct 942 ms 26448 KB Output is correct
21 Correct 967 ms 26792 KB Output is correct
22 Correct 933 ms 26568 KB Output is correct
23 Correct 968 ms 26356 KB Output is correct
24 Correct 393 ms 11932 KB Output is correct
25 Correct 343 ms 10788 KB Output is correct
26 Correct 302 ms 9236 KB Output is correct
27 Correct 263 ms 8604 KB Output is correct
28 Correct 236 ms 7760 KB Output is correct
29 Correct 204 ms 6996 KB Output is correct
30 Correct 65 ms 2744 KB Output is correct
31 Correct 274 ms 8960 KB Output is correct
32 Correct 44 ms 2132 KB Output is correct
33 Correct 129 ms 4948 KB Output is correct
34 Correct 109 ms 4176 KB Output is correct
35 Correct 115 ms 4436 KB Output is correct
36 Correct 3 ms 604 KB Output is correct
37 Correct 56 ms 2188 KB Output is correct
38 Correct 61 ms 2580 KB Output is correct
39 Correct 62 ms 2336 KB Output is correct
40 Correct 58 ms 2388 KB Output is correct
41 Correct 65 ms 2640 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 123 ms 4376 KB Output is correct
48 Correct 162 ms 4680 KB Output is correct
49 Correct 1 ms 600 KB Output is correct
50 Correct 2 ms 604 KB Output is correct
51 Correct 337 ms 10416 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 464 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Execution timed out 1600 ms 43552 KB Time limit exceeded
60 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 58 ms 2736 KB Output is correct
4 Execution timed out 1536 ms 46164 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 7 ms 800 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 9 ms 860 KB Output is correct
8 Correct 0 ms 412 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 853 ms 23888 KB Output is correct
16 Correct 732 ms 20280 KB Output is correct
17 Correct 811 ms 22056 KB Output is correct
18 Correct 948 ms 26960 KB Output is correct
19 Correct 955 ms 26788 KB Output is correct
20 Correct 942 ms 26448 KB Output is correct
21 Correct 967 ms 26792 KB Output is correct
22 Correct 933 ms 26568 KB Output is correct
23 Correct 968 ms 26356 KB Output is correct
24 Correct 393 ms 11932 KB Output is correct
25 Correct 343 ms 10788 KB Output is correct
26 Correct 302 ms 9236 KB Output is correct
27 Correct 263 ms 8604 KB Output is correct
28 Correct 236 ms 7760 KB Output is correct
29 Correct 204 ms 6996 KB Output is correct
30 Correct 65 ms 2744 KB Output is correct
31 Correct 274 ms 8960 KB Output is correct
32 Correct 44 ms 2132 KB Output is correct
33 Correct 129 ms 4948 KB Output is correct
34 Correct 109 ms 4176 KB Output is correct
35 Correct 115 ms 4436 KB Output is correct
36 Correct 3 ms 604 KB Output is correct
37 Correct 56 ms 2188 KB Output is correct
38 Correct 61 ms 2580 KB Output is correct
39 Correct 62 ms 2336 KB Output is correct
40 Correct 58 ms 2388 KB Output is correct
41 Correct 65 ms 2640 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 123 ms 4376 KB Output is correct
48 Correct 162 ms 4680 KB Output is correct
49 Correct 1 ms 600 KB Output is correct
50 Correct 2 ms 604 KB Output is correct
51 Correct 337 ms 10416 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 464 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Execution timed out 1600 ms 43552 KB Time limit exceeded
60 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 7 ms 800 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 9 ms 860 KB Output is correct
8 Correct 0 ms 412 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 853 ms 23888 KB Output is correct
16 Correct 732 ms 20280 KB Output is correct
17 Correct 811 ms 22056 KB Output is correct
18 Correct 948 ms 26960 KB Output is correct
19 Correct 955 ms 26788 KB Output is correct
20 Correct 942 ms 26448 KB Output is correct
21 Correct 967 ms 26792 KB Output is correct
22 Correct 933 ms 26568 KB Output is correct
23 Correct 968 ms 26356 KB Output is correct
24 Correct 393 ms 11932 KB Output is correct
25 Correct 343 ms 10788 KB Output is correct
26 Correct 302 ms 9236 KB Output is correct
27 Correct 263 ms 8604 KB Output is correct
28 Correct 236 ms 7760 KB Output is correct
29 Correct 204 ms 6996 KB Output is correct
30 Correct 65 ms 2744 KB Output is correct
31 Correct 274 ms 8960 KB Output is correct
32 Correct 44 ms 2132 KB Output is correct
33 Correct 129 ms 4948 KB Output is correct
34 Correct 109 ms 4176 KB Output is correct
35 Correct 115 ms 4436 KB Output is correct
36 Correct 3 ms 604 KB Output is correct
37 Correct 56 ms 2188 KB Output is correct
38 Correct 61 ms 2580 KB Output is correct
39 Correct 62 ms 2336 KB Output is correct
40 Correct 58 ms 2388 KB Output is correct
41 Correct 65 ms 2640 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 123 ms 4376 KB Output is correct
48 Correct 162 ms 4680 KB Output is correct
49 Correct 1 ms 600 KB Output is correct
50 Correct 2 ms 604 KB Output is correct
51 Correct 337 ms 10416 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 464 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Execution timed out 1600 ms 43552 KB Time limit exceeded
60 Halted 0 ms 0 KB -