Submission #1200986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200986		ppppp	Mecho (IOI09_mecho)	C++20	4 / 100	2 ms	3656 KiB

mecho

#include<bits/stdc++.h>
#define ll long long int
#define f first 
// #define s second 
using namespace std;
int di[4] = {0, 0, 1, -1};
int dj[4] = {-1, 1, 0, 0};

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, s;
    cin >> n >> s;
    vector<string> mat(n, "");
    vector<vector<int>> time(n, vector<int>(n, 0));
    int si, sj, ei, ej;
    queue<pair<int,pair<int,int>>> bag;
    vector<vector<bool>> v(n, vector<bool>(n, 0));
    for (int i = 0 ; i < n ; i++) cin >> mat[i];
    cout << -1;
    // for (int i = 0 ; i < n ; i++) { 
    //     for (int j = 0 ; j < n ; j++) {
    //         if (mat[i][j] == 'M') {
    //             si = i;
    //             sj = j;
    //         } else if (mat[i][j] == 'D') {
    //             ei = i;
    //             ej = j;
    //         } else if (mat[i][j] == 'H') {
    //             bag.push({0, {i, j}});
    //             v[i][j] = 1;
    //         }
    //     }
    // }
    // while(!bag.empty()) {
    //     int cnt = bag.front().first;
    //     int i = bag.front().second.first;
    //     int j = bag.front().second.second;
    //     bag.pop();
    //     for (int d = 0 ; d < 4 ; d++) {
    //         int nxi = i + di[d];
    //         int nxj = j + dj[d];
    //         if (nxi >= 0 && nxi < n && nxj >= 0 && nxj < n && mat[nxi][nxj] != 'T') {
    //             if (v[nxi][nxj]) continue;
    //             bag.push({cnt+1, {nxi, nxj}});
    //             v[nxi][nxj] = 1;
    //             time[nxi][nxj] = cnt+1;
    //         }   
    //     }
    // }
    // // for (int i = 0 ; i < n ; i++) {
    // //     for (int j = 0 ; j < n ; j++) cout << time[i][j] << ' ';
    // //     cout << endl;
    // // }
    // int l = 0;
    // int r = n*n;
    // // bool valid = 0;
    // vector<int> valid(n*n, 0);
    // while(l < r) {
    //     int mid = (l+r+1)/2;
    //     // cout << mid << endl;
    //     if (mid >= time[si][sj]) r = mid-1;
    //     else {
    //         bag.push({mid*s, {si, sj}});
    //         v.resize(0);
    //         v.resize(n, vector<bool>(n, 0));
    //         v[si][sj] = 1;
    //         // cout << bag.size() << endl;
    //         while(!bag.empty()) {
    //             int cnt = bag.front().first;
    //             int i = bag.front().second.first;
    //             int j = bag.front().second.second;
    //             // cout << i << ' ' << j << ' ' << cnt << endl;
    //             bag.pop();
    //             if (i == ei && j == ej) {
    //                 l = mid;
    //                 valid[l] = 1;
    //                 break;
    //             }
    //             for (int d = 0 ; d < 4 ; d++) {
    //                 int nxi = i + di[d];
    //                 int nxj = j + dj[d];
    //                 if (nxi >= 0 && nxi < n && nxj >= 0 && nxj < n && mat[nxi][nxj] != 'T') {
    //                     if (!v[nxi][nxj] && (cnt+1) / s < time[nxi][nxj]) {
    //                         bag.push({cnt+1, {nxi, nxj}});
    //                         v[nxi][nxj] = 1;
    //                     }
    //                 }
    //             }
    //         }
    //         if (bag.empty()) r = mid-1;
    //         else {
    //             while(!bag.empty()) {
    //                 bag.pop();
    //             }
    //         }
    //     }
    // }
    // if (valid[l]) cout << l;
    // else cout << -1;
}

• Subtask 1: 4 / 100