oj.uz

Submission #655543

# Submission time Handle Problem Language Result Execution time Memory
655543 2022-11-04T16:55:20 Z veiga Mecho (IOI09_mecho) C++17
56 / 100
 1000 ms 5560 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
#define endl "\n"
const int INF = 1e9+10;
const int MOD = 1e9+7;

int n, k;
vector<string> base;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void print(vector<string> s) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cout << s[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

bool bfs(int p) {
    vector<string> at = base;
    priority_queue<tuple<int, int, int, int>> q;
    // talvez a pq sem o tipo de op fique bugado!
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(at[i][j] == 'H') q.push({-(k-1), 0, i, j});
            if(at[i][j] == 'M') q.push({-(k*p), 1, i, j});
            // cout << -((p-1) * k) << endl;
        }
    }
    while(!q.empty()) {
        int x, y, t, user;
        tie(t, user, x, y) = q.top(); q.pop();
        t = -t;
        for(int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx < 0 or xx >= n or yy < 0 or yy >= n) continue;
            if(at[x][y] == 'M' and user == 1) {
                if(at[xx][yy] == 'G') {
                    at[xx][yy] = 'M';
                    q.push({-(t + 1), 1, xx, yy});
                    // cout << -(t + 1) << " " << 1 << endl;
                }
                if(at[xx][yy] == 'D') {
                    return true;
                }
            }
            if(at[x][y] == 'H' and user == 0) {
                if(at[xx][yy] == 'G' or at[xx][yy] == 'M') {
                    at[xx][yy] = 'H';
                    q.push({-(t + k), 0, xx, yy});
                    // cout << -(t + k) << " " << 0 << endl;
                }
            }
        }
        // print(at);
        // cout << user << " " << t << endl;
    }
    return false;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        string s; cin >> s;
        base.pb(s);
    }
    int l = 0, r = 100000, resp = -1;
    while(l <= r) {
        int m = (l+r)/2;
        // cout << m << " " << bfs(m) << endl;
        if(bfs(m)) {
            resp = m;
            l = m+1;
        } else {
            r = m-1;
        }
    }
    cout << resp << endl;

    return 0;
}

Subtask #1
56.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Execution timed out 1082 ms 3296 KB Time limit exceeded
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 7 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 320 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 324 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 2 ms 324 KB Output is correct
28 Correct 2 ms 356 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 320 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct
33 Correct 31 ms 596 KB Output is correct
34 Correct 37 ms 724 KB Output is correct
35 Correct 180 ms 796 KB Output is correct
36 Correct 43 ms 844 KB Output is correct
37 Correct 45 ms 868 KB Output is correct
38 Correct 240 ms 948 KB Output is correct
39 Incorrect 51 ms 968 KB Output isn't correct
40 Correct 52 ms 964 KB Output is correct
41 Correct 308 ms 1008 KB Output is correct
42 Incorrect 51 ms 1108 KB Output isn't correct
43 Correct 72 ms 1132 KB Output is correct
44 Correct 381 ms 1248 KB Output is correct
45 Incorrect 53 ms 1360 KB Output isn't correct
46 Correct 83 ms 1252 KB Output is correct
47 Correct 484 ms 1320 KB Output is correct
48 Incorrect 56 ms 1456 KB Output isn't correct
49 Correct 100 ms 1452 KB Output is correct
50 Correct 558 ms 1784 KB Output is correct
51 Incorrect 55 ms 1640 KB Output isn't correct
52 Incorrect 115 ms 1640 KB Output isn't correct
53 Correct 692 ms 1688 KB Output is correct
54 Incorrect 65 ms 1860 KB Output isn't correct
55 Incorrect 141 ms 1828 KB Output isn't correct
56 Correct 776 ms 2168 KB Output is correct
57 Incorrect 63 ms 2064 KB Output isn't correct
58 Incorrect 112 ms 2056 KB Output isn't correct
59 Correct 896 ms 2120 KB Output is correct
60 Incorrect 60 ms 2276 KB Output isn't correct
61 Incorrect 117 ms 2284 KB Output isn't correct
62 Execution timed out 1051 ms 2504 KB Time limit exceeded
63 Correct 904 ms 2400 KB Output is correct
64 Correct 807 ms 2400 KB Output is correct
65 Correct 878 ms 2432 KB Output is correct
66 Correct 818 ms 2508 KB Output is correct
67 Correct 899 ms 2456 KB Output is correct
68 Correct 948 ms 2676 KB Output is correct
69 Correct 796 ms 2580 KB Output is correct
70 Correct 908 ms 2580 KB Output is correct
71 Correct 923 ms 2660 KB Output is correct
72 Correct 848 ms 2600 KB Output is correct
73 Execution timed out 1073 ms 5520 KB Time limit exceeded
74 Execution timed out 1077 ms 5512 KB Time limit exceeded
75 Execution timed out 1087 ms 5444 KB Time limit exceeded
76 Execution timed out 1063 ms 5560 KB Time limit exceeded
77 Execution timed out 1084 ms 5404 KB Time limit exceeded
78 Execution timed out 1089 ms 4336 KB Time limit exceeded
79 Execution timed out 1090 ms 4324 KB Time limit exceeded
80 Execution timed out 1089 ms 4356 KB Time limit exceeded
81 Execution timed out 1079 ms 4448 KB Time limit exceeded
82 Execution timed out 1090 ms 4248 KB Time limit exceeded
83 Execution timed out 1079 ms 4364 KB Time limit exceeded
84 Execution timed out 1082 ms 4108 KB Time limit exceeded
85 Execution timed out 1078 ms 4180 KB Time limit exceeded
86 Execution timed out 1089 ms 4144 KB Time limit exceeded
87 Execution timed out 1084 ms 4208 KB Time limit exceeded
88 Execution timed out 1088 ms 4072 KB Time limit exceeded
89 Execution timed out 1083 ms 3988 KB Time limit exceeded
90 Execution timed out 1081 ms 3920 KB Time limit exceeded
91 Execution timed out 1080 ms 3932 KB Time limit exceeded
92 Execution timed out 1083 ms 4012 KB Time limit exceeded