Submission #655545

#	Time	Username	Problem	Language	Result	Execution time	Memory
655545		veiga	Mecho (IOI09_mecho)	C++17	45 / 100	1094 ms	4888 KiB

mecho

#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 = 1000, 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: 45 / 100