Submission #810475

#	Time	Username	Problem	Language	Result	Execution time	Memory
810475		asdasdqwer	Mecho (IOI09_mecho)	C++17	100 / 100	530 ms	17004 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define mp make_pair
#define pii pair<int, int>
#define f first
#define s second
#define tii array<int, 3>
#define all(x) x.begin(), x.end()
#define pb push_back
#define ppi pair<pii, int>

vector<pii> dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

pii operator+(const pii &x, const pii &y) {
    return mp(x.f+y.f, x.s+y.s);
}

bool check(const pii &x, int n) {
    return x.f >= 0 && x.f < n && x.s >= 0 && x.s < n;
}

// void printArr(vector<vector<int>> &a) {
//     int n = a.size();
//     for (int i=0;i<n;i++) {
//         fmt::print("{}\n", a[i]);
//     }
// }

bool test(int wait, vector<vector<int>> &grid, int st, pii &pos, pii &des) {
    // simulate "wait"
    int n=grid.size();
    vector<vector<int>> status(n, vector<int>(n, 0));
    queue<pair<pii, int>> q;
    vector<pii> hv;
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            if (grid[i][j]==0) {
                hv.pb(mp(i, j));
            }
        }
    }

    for (auto &x:hv) {
        q.push(mp(x, 0));
        status[x.f][x.s]=1;
    }

    while (!q.empty() && q.front().s != wait) {
        ppi t = q.front();q.pop();
        if (t.s != wait) {
            for (int i=0;i<4;i++) {
                pii add = t.f + dir[i];
                if (check(add, n) && status[add.f][add.s] != 1 && grid[add.f][add.s]==1) {
                    status[add.f][add.s]=1;
                    q.push(mp(add, t.s+1));
                }
            }
        }
    }

    queue<ppi> pq;
    pq.push(mp(pos, 0));
    int endB = wait;
    int endP = 0;
    while (true) {
        endB++;endP+=st;
        if (pq.empty()) return false;
        while (!pq.empty() && pq.front().s != endP) {
            ppi t=pq.front();pq.pop();
            if (t.f==des) {
                return true;
            }

            if (status[t.f.f][t.f.s]==1) {
                continue;
            }

            for (int i=0;i<4;i++) {
                pii add=t.f + dir[i];
                if (check(add, n) && (status[add.f][add.s]==0) && grid[add.f][add.s]==1) {
                    status[add.f][add.s]=2;
                    pq.push(mp(add, t.s+1));
                }

                else if (check(add, n) && add==des) {
                    return true;
                } 
            }
        }

        while (!q.empty() && q.front().s != endB) {
            ppi t = q.front();q.pop();
            if (t.s != endB) {
                for (int i=0;i<4;i++) {
                    pii add = t.f + dir[i];
                    if (check(add, n) && status[add.f][add.s] != 1 && grid[add.f][add.s]==1) {
                        status[add.f][add.s]=1;
                        q.push(mp(add, t.s+1));
                    }
                }
            }
        }
    }
}

int binSearch(vector<vector<int>> a, int st, pii &pos, pii &des) {
    int n = a.size();
    int l = 0, r = 2*(n*n);

    int ans = -1;
    while (l <= r) {
        int m = l + (r-l)/2;
        bool t = test(m, a, st, pos, des);
        // cout << m << " " << t << "\n";
        if (t) {
            l = m+1;
            ans = m;
        }

        else {
            r = m-1;
        }
    }

    return ans;
}

signed main() {
    // freopen("in.txt", "r", stdin);
    int n, st;cin>>n>>st;
    vector<vector<int>> a(n, vector<int>(n, 0));
    pii pos, des;
    for (int i=0;i<n;i++) {
        string s;cin>>s;
        for (int j=0;j<n;j++) {
            if (s[j]=='H')a[i][j]=0;
            if (s[j]=='G')a[i][j]=1;
            if (s[j]=='M') {
                a[i][j]=1;
                pos=mp(i, j);
            }

            if (s[j]=='D') {
                a[i][j]=-1;
                des=mp(i, j);
            }

            if (s[j]=='T')a[i][j]=-1;
        }
    }
    // cout << test(0, a, st, pos, des) << "\n";
    cout << binSearch(a, st, pos, des) << "\n";
}

• Subtask 1: 100 / 100