oj.uz

Submission #762779

# Submission time Handle Problem Language Result Execution time Memory
762779 2023-06-21T18:49:21 Z bLIC Mecho (IOI09_mecho) C++17
2 / 100
 228 ms 6348 KB 
/**
 *  Author: Anil Byar
**/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

// template<class T>
// using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;



#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define uniq(v) v.erase(unique(all(v)), v.end())
#define ft first
#define sd second
#define pb push_back
#define eb emplace_back

// Source: https://codeforces.com/blog/entry/68809
// { start
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// } end


typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;

#define dbg if(0)

const ll MOD = 1e9+7;
const ll MOD9 = 998244353;
const ll INFLL = 1e18+5;
const int INF = 1e9;

void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}
ll power(ll x, ll y, ll mod){if (y==0) return 1;ll ret = power(x, y/2, mod);ret *= ret;ret%=mod;if (y&1) ret *= x;return ret%mod;}
ll modinv(ll x, ll mod = MOD) {return power(x, mod-2, mod);}

template<class T>
istream& operator>>(istream&in, vector<T>&v){
    for (T& x:v) in>>x;
    return in;
}
template<class T>
ostream& operator<<(ostream&out, vector<T>&v){
    for (T& x:v) out<<x<<' ';
    cout<<'\n';
    return out;
}
// use ?: with brackets (?:)
// check for overflow
// think about dp
// Read the statement carefully

const int maxN = 1;
const int maxK = 8001;

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

void solve(){
    int n, s;cin>>n>>s;
    vector<string> grid(n);
    for (int i = 0;i<n;i++) cin>>grid[i];

    vvi beetime(n, vi(n, INF));
    queue<pii> q;
    for (int i = 0;i<n;i++) for (int j = 0;j<n;j++) if (grid[i][j]=='H') {
        q.emplace(i, j);
        beetime[i][j] = 0;
    }
    while(!q.empty()){
        auto [x, y] = q.front();q.pop();
        int tim = beetime[x][y] + 1;
        for (int i = 0;i<4;i++){
            int xx = x+dx[i];
            int yy = y+dy[i];
            if (xx<0 || xx>=n || yy<0 || yy>=n || tim>=beetime[xx][yy] || grid[xx][yy]=='T' || grid[xx][yy]=='D'){
                continue;
            }
            beetime[xx][yy] = tim;
            q.emplace(xx, yy);
        }
    }

    auto check = [&](int m){
        vvi mtim(n, vi(n, INF));
        queue<array<int, 3>> qq;
        int fx, fy;
        for (int i = 0;i<n;i++){
            for (int j = 0;j<n;j++){
                if (grid[i][j]=='M'){
                    qq.push({i, j, 0});
                    mtim[i][j] = m;
                } else if (grid[i][j]=='D') fx=i, fy = j;
            }
        }
        vector<vector<bool>> poss(n, vector<bool>(n, false));

        while(!qq.empty()){
            auto [x, y, step] = qq.front();qq.pop();
            poss[x][y] = true;
            step++;
            int tim = mtim[x][y];
            if (step==1) tim++;
            if (step==s) step = 0;
            for (int i = 0;i<4;i++){
                int xx = x+dx[i];
                int yy = y+dy[i];
                if (xx<0 || yy<0 || xx>=n || yy>=n || grid[xx][yy]=='T' || tim>beetime[xx][yy] || tim>=mtim[xx][yy]){
                    continue;
                }
                mtim[xx][yy] = tim;
                qq.push({xx, yy, step});
            }
        }
        if (poss[fx][fy]) return true;

        mtim.assign(n, vi(n, INF));
        mtim[fx][fy] = 0;

        while(!q.empty()) q.pop();
        q.emplace(fx, fy);
    
        while(!q.empty()){
            auto [x, y] = q.front();q.pop();
            if (poss[x][y]) return true;

            int tim = mtim[x][y] + 1;
            for (int i = 0;i<4;i++){
                int xx = x+dx[i];
                int yy = y+dy[i];
                if (xx<0 || xx>=n || yy<0 || yy>=n || grid[xx][yy]=='T' || tim>= mtim[xx][yy] || tim>s){
                    continue;
                }
                mtim[xx][yy] = tim;
                q.emplace(xx, yy);
            }
        }
        
        return false;
    };

    int l = -1, r = INF;
    while(r-l>1){
        int mid = (l+r)/2;
        if (check(mid)) l = mid;
        else r = mid;
    } 
    cout<<l;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    freopen("debug.dbg", "w", stderr);
    int tt = clock();
#endif

    int t=1, i = 1;
    // cin>>t;
    while(t--){
        // cout<<"Case #"<<i++<<": ";
        solve();
        cout<<'\n';
    }
#ifndef ONLINE_JUDGE
    cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
    tt = clock();
#endif
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:207:14: warning: unused variable 'i' [-Wunused-variable]
  207 |     int t=1, i = 1;
      |              ^

Subtask #1
2.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 94 ms 6240 KB Output isn't correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Incorrect 0 ms 212 KB Output isn't correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Incorrect 1 ms 212 KB Output isn't correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Incorrect 1 ms 340 KB Output isn't correct
24 Incorrect 1 ms 340 KB Output isn't correct
25 Incorrect 1 ms 340 KB Output isn't correct
26 Incorrect 1 ms 340 KB Output isn't correct
27 Incorrect 1 ms 340 KB Output isn't correct
28 Incorrect 1 ms 340 KB Output isn't correct
29 Incorrect 1 ms 340 KB Output isn't correct
30 Incorrect 1 ms 340 KB Output isn't correct
31 Incorrect 1 ms 340 KB Output isn't correct
32 Incorrect 1 ms 340 KB Output isn't correct
33 Incorrect 9 ms 1472 KB Output isn't correct
34 Incorrect 10 ms 1468 KB Output isn't correct
35 Incorrect 42 ms 1476 KB Output isn't correct
36 Incorrect 11 ms 1816 KB Output isn't correct
37 Incorrect 11 ms 1844 KB Output isn't correct
38 Incorrect 55 ms 1860 KB Output isn't correct
39 Incorrect 13 ms 2216 KB Output isn't correct
40 Incorrect 14 ms 2236 KB Output isn't correct
41 Incorrect 70 ms 2204 KB Output isn't correct
42 Incorrect 16 ms 2704 KB Output isn't correct
43 Incorrect 17 ms 2644 KB Output isn't correct
44 Incorrect 82 ms 2652 KB Output isn't correct
45 Incorrect 20 ms 3140 KB Output isn't correct
46 Incorrect 21 ms 3140 KB Output isn't correct
47 Incorrect 100 ms 3028 KB Output isn't correct
48 Incorrect 24 ms 3692 KB Output isn't correct
49 Incorrect 24 ms 3704 KB Output isn't correct
50 Incorrect 131 ms 3660 KB Output isn't correct
51 Incorrect 33 ms 4248 KB Output isn't correct
52 Incorrect 28 ms 4220 KB Output isn't correct
53 Incorrect 140 ms 4220 KB Output isn't correct
54 Incorrect 32 ms 4844 KB Output isn't correct
55 Incorrect 35 ms 4844 KB Output isn't correct
56 Incorrect 171 ms 4828 KB Output isn't correct
57 Incorrect 34 ms 5528 KB Output isn't correct
58 Incorrect 36 ms 5520 KB Output isn't correct
59 Incorrect 183 ms 5460 KB Output isn't correct
60 Incorrect 38 ms 6240 KB Output isn't correct
61 Incorrect 40 ms 6216 KB Output isn't correct
62 Incorrect 228 ms 6204 KB Output isn't correct
63 Correct 117 ms 6348 KB Output is correct
64 Correct 187 ms 6224 KB Output is correct
65 Correct 165 ms 6252 KB Output is correct
66 Incorrect 122 ms 6260 KB Output isn't correct
67 Correct 116 ms 6252 KB Output is correct
68 Correct 68 ms 6264 KB Output is correct
69 Correct 69 ms 6284 KB Output is correct
70 Correct 57 ms 6336 KB Output is correct
71 Correct 58 ms 6272 KB Output is correct
72 Incorrect 57 ms 6268 KB Output isn't correct
73 Incorrect 60 ms 6296 KB Output isn't correct
74 Incorrect 147 ms 6100 KB Output isn't correct
75 Incorrect 81 ms 6256 KB Output isn't correct
76 Incorrect 77 ms 6276 KB Output isn't correct
77 Incorrect 79 ms 6276 KB Output isn't correct
78 Incorrect 99 ms 6324 KB Output isn't correct
79 Incorrect 178 ms 6216 KB Output isn't correct
80 Incorrect 78 ms 6280 KB Output isn't correct
81 Incorrect 88 ms 6248 KB Output isn't correct
82 Incorrect 75 ms 6252 KB Output isn't correct
83 Incorrect 98 ms 6272 KB Output isn't correct
84 Incorrect 188 ms 6204 KB Output isn't correct
85 Incorrect 83 ms 6264 KB Output isn't correct
86 Incorrect 89 ms 6276 KB Output isn't correct
87 Incorrect 90 ms 6284 KB Output isn't correct
88 Incorrect 92 ms 6252 KB Output isn't correct
89 Incorrect 191 ms 6116 KB Output isn't correct
90 Incorrect 93 ms 6260 KB Output isn't correct
91 Incorrect 88 ms 6260 KB Output isn't correct
92 Incorrect 101 ms 6248 KB Output isn't correct