oj.uz

Submission #762790

# Submission time Handle Problem Language Result Execution time Memory
762790 2023-06-21T19:06:59 Z bLIC Mecho (IOI09_mecho) C++17
24 / 100
 191 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();
            int tim = mtim[x][y];
            if (step==0) tim++;
            if (step==s) {
                step = 0;
                if (beetime[x][y]==mtim[x][y]) continue;
            }
            poss[x][y] = true;
            step++;
            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:210:14: warning: unused variable 'i' [-Wunused-variable]
  210 |     int t=1, i = 1;
      |              ^
mecho.cpp: In function 'void solve()':
mecho.cpp:160:20: warning: 'fx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  160 |         if (poss[fx][fy]) return true;
      |                    ^

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Incorrect 95 ms 6224 KB Output isn't correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 292 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 9 ms 1512 KB Output is correct
34 Correct 9 ms 1512 KB Output is correct
35 Incorrect 25 ms 1488 KB Output isn't correct
36 Correct 9 ms 1816 KB Output is correct
37 Correct 11 ms 1932 KB Output is correct
38 Incorrect 28 ms 1816 KB Output isn't correct
39 Correct 12 ms 2268 KB Output is correct
40 Correct 12 ms 2264 KB Output is correct
41 Incorrect 36 ms 2216 KB Output isn't correct
42 Correct 14 ms 2648 KB Output is correct
43 Correct 14 ms 2648 KB Output is correct
44 Incorrect 49 ms 2644 KB Output isn't correct
45 Correct 22 ms 3164 KB Output is correct
46 Correct 17 ms 3120 KB Output is correct
47 Incorrect 57 ms 3192 KB Output isn't correct
48 Correct 21 ms 3712 KB Output is correct
49 Correct 22 ms 3716 KB Output is correct
50 Incorrect 69 ms 3764 KB Output isn't correct
51 Correct 24 ms 4256 KB Output is correct
52 Correct 25 ms 4220 KB Output is correct
53 Incorrect 79 ms 4228 KB Output isn't correct
54 Correct 31 ms 4872 KB Output is correct
55 Correct 31 ms 4868 KB Output is correct
56 Incorrect 110 ms 4836 KB Output isn't correct
57 Correct 31 ms 5500 KB Output is correct
58 Correct 31 ms 5536 KB Output is correct
59 Incorrect 107 ms 5544 KB Output isn't correct
60 Correct 34 ms 6244 KB Output is correct
61 Correct 35 ms 6212 KB Output is correct
62 Incorrect 121 ms 6320 KB Output isn't correct
63 Incorrect 152 ms 6256 KB Output isn't correct
64 Correct 172 ms 6316 KB Output is correct
65 Incorrect 191 ms 6252 KB Output isn't correct
66 Incorrect 133 ms 6240 KB Output isn't correct
67 Incorrect 156 ms 6248 KB Output isn't correct
68 Incorrect 65 ms 6232 KB Output isn't correct
69 Incorrect 62 ms 6220 KB Output isn't correct
70 Incorrect 78 ms 6260 KB Output isn't correct
71 Incorrect 66 ms 6340 KB Output isn't correct
72 Correct 49 ms 6240 KB Output is correct
73 Correct 75 ms 6300 KB Output is correct
74 Correct 75 ms 6260 KB Output is correct
75 Incorrect 82 ms 6328 KB Output isn't correct
76 Incorrect 71 ms 6264 KB Output isn't correct
77 Incorrect 78 ms 6268 KB Output isn't correct
78 Incorrect 85 ms 6244 KB Output isn't correct
79 Correct 73 ms 6268 KB Output is correct
80 Incorrect 77 ms 6304 KB Output isn't correct
81 Incorrect 80 ms 6240 KB Output isn't correct
82 Incorrect 92 ms 6240 KB Output isn't correct
83 Incorrect 93 ms 6252 KB Output isn't correct
84 Correct 83 ms 6260 KB Output is correct
85 Incorrect 74 ms 6256 KB Output isn't correct
86 Incorrect 90 ms 6324 KB Output isn't correct
87 Incorrect 83 ms 6340 KB Output isn't correct
88 Incorrect 89 ms 6328 KB Output isn't correct
89 Correct 96 ms 6348 KB Output is correct
90 Incorrect 91 ms 6264 KB Output isn't correct
91 Incorrect 90 ms 6276 KB Output isn't correct
92 Incorrect 97 ms 6320 KB Output isn't correct