oj.uz

Submission #1097083

# Submission time Handle Problem Language Result Execution time Memory
1097083 2024-10-06T03:30:36 Z InvMOD Mecho (IOI09_mecho) C++14
21 / 100
 228 ms 6396 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 8e2+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int n, s, d[N][N], vis[N][N];
char a[N][N];

bool init(int x, int y){
    return (x >= 1 && x <= n) && (y >= 1 && y <= n) && a[x][y] != 'T';
}

bool good(int time){
    pi st, ed;
    FOR(i, 1, n){
        FOR(j, 1, n){
            if(a[i][j] == 'M'){
                st = make_pair(i,j);
                vis[i][j] = time*s;
            }
            else{
                if(a[i][j] == 'D'){
                    ed = make_pair(i, j);
                }
                vis[i][j] = 1e9;
            }
        }
    }

    queue<pair<int,int>> q;
    q.push(st);

    while(sz(q)){
        pi e = q.front(); q.pop();

        int x = e.fi, y = e.se;
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(init(xx, yy) && vis[xx][yy] == 1e9 && a[xx][yy] != 'H'){
                int n_dist = (vis[x][y] + 1) / s;
                if(n_dist < d[xx][yy]){
                    vis[xx][yy] = vis[x][y] + 1;
                    q.push(make_pair(xx, yy));
                }
            }
        }
    }

    return vis[ed.fi][ed.se] != 1e9;
}

void solve()
{
    cin >> n >> s;
    FOR(i, 1, n){
        FOR(j, 1, n){
            cin >> a[i][j];
        }
    }

    queue<pair<int,int>> q;

    FOR(i, 1, n){
        FOR(j, 1, n){
            if(a[i][j] == 'H'){
                q.push(make_pair(i,j));
            }
            else d[i][j] = 1e9;
        }
    }

    while(sz(q)){
        pi e = q.front(); q.pop();

        int x = e.fi, y = e.se;
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(init(xx, yy) && d[xx][yy] == 1e9 && a[xx][yy] != 'D'){
                d[xx][yy] = d[x][y] + 1;
                q.push(make_pair(xx, yy));
            }
        }
    }



    int l = -1, r = 1e9;
    while(l+1 < r){
        int m = l+r>>1;
        if(good(m)){
            l = m;
        }
        else r = m;
    }
    cout << l <<"\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message

mecho.cpp: In function 'void solve()':
mecho.cpp:114:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         int m = l+r>>1;
      |                 ~^~
mecho.cpp: In function 'int main()':
mecho.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 176 ms 6236 KB Output isn't correct
8 Correct 0 ms 344 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 1 ms 860 KB Output isn't correct
13 Incorrect 0 ms 604 KB Output isn't correct
14 Incorrect 2 ms 860 KB Output isn't correct
15 Correct 0 ms 604 KB Output is correct
16 Incorrect 1 ms 600 KB Output isn't correct
17 Correct 0 ms 604 KB Output is correct
18 Incorrect 0 ms 604 KB Output isn't correct
19 Correct 0 ms 600 KB Output is correct
20 Incorrect 1 ms 600 KB Output isn't correct
21 Correct 1 ms 604 KB Output is correct
22 Incorrect 0 ms 604 KB Output isn't correct
23 Correct 0 ms 604 KB Output is correct
24 Incorrect 1 ms 604 KB Output isn't correct
25 Correct 1 ms 724 KB Output is correct
26 Incorrect 1 ms 860 KB Output isn't correct
27 Correct 1 ms 860 KB Output is correct
28 Incorrect 1 ms 940 KB Output isn't correct
29 Correct 1 ms 860 KB Output is correct
30 Incorrect 1 ms 860 KB Output isn't correct
31 Correct 1 ms 860 KB Output is correct
32 Incorrect 1 ms 860 KB Output isn't correct
33 Correct 7 ms 2872 KB Output is correct
34 Incorrect 13 ms 2960 KB Output isn't correct
35 Incorrect 37 ms 3156 KB Output isn't correct
36 Correct 14 ms 3168 KB Output is correct
37 Incorrect 15 ms 3164 KB Output isn't correct
38 Incorrect 47 ms 3252 KB Output isn't correct
39 Correct 9 ms 3420 KB Output is correct
40 Incorrect 17 ms 3656 KB Output isn't correct
41 Incorrect 52 ms 3416 KB Output isn't correct
42 Correct 11 ms 3932 KB Output is correct
43 Incorrect 23 ms 3976 KB Output isn't correct
44 Incorrect 76 ms 3932 KB Output isn't correct
45 Correct 16 ms 4188 KB Output is correct
46 Incorrect 30 ms 4188 KB Output isn't correct
47 Incorrect 80 ms 4188 KB Output isn't correct
48 Correct 16 ms 4696 KB Output is correct
49 Incorrect 33 ms 4700 KB Output isn't correct
50 Incorrect 115 ms 4700 KB Output isn't correct
51 Correct 20 ms 4952 KB Output is correct
52 Incorrect 29 ms 4952 KB Output isn't correct
53 Incorrect 121 ms 4956 KB Output isn't correct
54 Correct 22 ms 5208 KB Output is correct
55 Incorrect 40 ms 5212 KB Output isn't correct
56 Incorrect 121 ms 5208 KB Output isn't correct
57 Correct 23 ms 5720 KB Output is correct
58 Incorrect 53 ms 5720 KB Output isn't correct
59 Incorrect 130 ms 5764 KB Output isn't correct
60 Correct 31 ms 5980 KB Output is correct
61 Incorrect 58 ms 6120 KB Output isn't correct
62 Incorrect 174 ms 5976 KB Output isn't correct
63 Correct 81 ms 5980 KB Output is correct
64 Incorrect 225 ms 6232 KB Output isn't correct
65 Correct 123 ms 5980 KB Output is correct
66 Correct 91 ms 6120 KB Output is correct
67 Correct 83 ms 5980 KB Output is correct
68 Incorrect 176 ms 6144 KB Output isn't correct
69 Incorrect 159 ms 6152 KB Output isn't correct
70 Incorrect 200 ms 6204 KB Output isn't correct
71 Incorrect 191 ms 6148 KB Output isn't correct
72 Incorrect 145 ms 5972 KB Output isn't correct
73 Incorrect 185 ms 6396 KB Output isn't correct
74 Incorrect 142 ms 6224 KB Output isn't correct
75 Incorrect 156 ms 6396 KB Output isn't correct
76 Incorrect 155 ms 6396 KB Output isn't correct
77 Incorrect 156 ms 6208 KB Output isn't correct
78 Incorrect 186 ms 6224 KB Output isn't correct
79 Incorrect 169 ms 6380 KB Output isn't correct
80 Incorrect 154 ms 6236 KB Output isn't correct
81 Incorrect 130 ms 6236 KB Output isn't correct
82 Incorrect 157 ms 6228 KB Output isn't correct
83 Incorrect 180 ms 6336 KB Output isn't correct
84 Incorrect 158 ms 6236 KB Output isn't correct
85 Incorrect 128 ms 6224 KB Output isn't correct
86 Incorrect 162 ms 6236 KB Output isn't correct
87 Incorrect 139 ms 6232 KB Output isn't correct
88 Incorrect 170 ms 6280 KB Output isn't correct
89 Incorrect 152 ms 6232 KB Output isn't correct
90 Incorrect 228 ms 6232 KB Output isn't correct
91 Incorrect 178 ms 6284 KB Output isn't correct
92 Incorrect 175 ms 6228 KB Output isn't correct