답안 #762772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762772	2023-06-21T18:42:52 Z	bLIC	Mecho (IOI09_mecho)	C++17	18 / 100	1000 ms	65536 KB

mecho

/**
 *  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;
        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>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:205:14: warning: unused variable 'i' [-Wunused-variable]
  205 |     int t=1, i = 1;
      |              ^

Subtask #1

18.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	316 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Incorrect	1 ms	212 KB	Output isn't correct
6	Incorrect	1 ms	212 KB	Output isn't correct
7	Runtime error	111 ms	65536 KB	Execution killed with signal 9
8	Correct	1 ms	212 KB	Output is correct
9	Incorrect	60 ms	1108 KB	Output isn't correct
10	Incorrect	1 ms	212 KB	Output isn't correct
11	Incorrect	1 ms	212 KB	Output isn't correct
12	Incorrect	2 ms	340 KB	Output isn't correct
13	Correct	1 ms	340 KB	Output is correct
14	Incorrect	1 ms	320 KB	Output isn't correct
15	Correct	1 ms	212 KB	Output is correct
16	Incorrect	6 ms	340 KB	Output isn't correct
17	Correct	1 ms	312 KB	Output is correct
18	Incorrect	64 ms	1732 KB	Output isn't correct
19	Correct	1 ms	212 KB	Output is correct
20	Incorrect	389 ms	5268 KB	Output isn't correct
21	Correct	1 ms	340 KB	Output is correct
22	Runtime error	156 ms	65536 KB	Execution killed with signal 9
23	Correct	1 ms	340 KB	Output is correct
24	Runtime error	156 ms	65536 KB	Execution killed with signal 9
25	Correct	1 ms	340 KB	Output is correct
26	Runtime error	154 ms	65536 KB	Execution killed with signal 9
27	Correct	1 ms	340 KB	Output is correct
28	Runtime error	154 ms	65536 KB	Execution killed with signal 9
29	Correct	1 ms	328 KB	Output is correct
30	Runtime error	173 ms	65536 KB	Execution killed with signal 9
31	Correct	1 ms	340 KB	Output is correct
32	Runtime error	155 ms	65536 KB	Execution killed with signal 9
33	Correct	9 ms	1628 KB	Output is correct
34	Runtime error	156 ms	65536 KB	Execution killed with signal 9
35	Runtime error	110 ms	65536 KB	Execution killed with signal 9
36	Correct	13 ms	1980 KB	Output is correct
37	Runtime error	154 ms	65536 KB	Execution killed with signal 9
38	Runtime error	114 ms	65536 KB	Execution killed with signal 9
39	Correct	17 ms	2412 KB	Output is correct
40	Runtime error	158 ms	65536 KB	Execution killed with signal 9
41	Runtime error	109 ms	65536 KB	Execution killed with signal 9
42	Correct	18 ms	2896 KB	Output is correct
43	Runtime error	154 ms	65536 KB	Execution killed with signal 9
44	Runtime error	130 ms	65536 KB	Execution killed with signal 9
45	Correct	21 ms	3424 KB	Output is correct
46	Runtime error	155 ms	65536 KB	Execution killed with signal 9
47	Runtime error	114 ms	65536 KB	Execution killed with signal 9
48	Correct	25 ms	3944 KB	Output is correct
49	Runtime error	151 ms	65536 KB	Execution killed with signal 9
50	Runtime error	113 ms	65536 KB	Execution killed with signal 9
51	Correct	27 ms	4496 KB	Output is correct
52	Runtime error	169 ms	65536 KB	Execution killed with signal 9
53	Runtime error	111 ms	65536 KB	Execution killed with signal 9
54	Correct	37 ms	5116 KB	Output is correct
55	Runtime error	153 ms	65536 KB	Execution killed with signal 9
56	Runtime error	109 ms	65536 KB	Execution killed with signal 9
57	Correct	35 ms	5748 KB	Output is correct
58	Runtime error	153 ms	65536 KB	Execution killed with signal 9
59	Runtime error	111 ms	65536 KB	Execution killed with signal 9
60	Correct	52 ms	6460 KB	Output is correct
61	Runtime error	153 ms	65536 KB	Execution killed with signal 9
62	Runtime error	116 ms	65536 KB	Execution killed with signal 9
63	Incorrect	110 ms	6504 KB	Output isn't correct
64	Runtime error	166 ms	65536 KB	Execution killed with signal 9
65	Incorrect	164 ms	6484 KB	Output isn't correct
66	Correct	127 ms	6496 KB	Output is correct
67	Correct	132 ms	6500 KB	Output is correct
68	Runtime error	149 ms	65536 KB	Execution killed with signal 9
69	Runtime error	154 ms	65536 KB	Execution killed with signal 9
70	Incorrect	553 ms	12184 KB	Output isn't correct
71	Incorrect	54 ms	6480 KB	Output isn't correct
72	Runtime error	150 ms	65536 KB	Execution killed with signal 9
73	Correct	77 ms	6704 KB	Output is correct
74	Runtime error	115 ms	65536 KB	Execution killed with signal 9
75	Runtime error	232 ms	65536 KB	Execution killed with signal 9
76	Incorrect	71 ms	6628 KB	Output isn't correct
77	Runtime error	128 ms	65536 KB	Execution killed with signal 9
78	Execution timed out	1084 ms	54708 KB	Time limit exceeded
79	Runtime error	113 ms	65536 KB	Execution killed with signal 9
80	Execution timed out	1076 ms	54708 KB	Time limit exceeded
81	Incorrect	260 ms	58532 KB	Output isn't correct
82	Runtime error	113 ms	65536 KB	Execution killed with signal 9
83	Execution timed out	1012 ms	19220 KB	Time limit exceeded
84	Runtime error	122 ms	65536 KB	Execution killed with signal 9
85	Runtime error	111 ms	65536 KB	Execution killed with signal 9
86	Runtime error	114 ms	65536 KB	Execution killed with signal 9
87	Runtime error	115 ms	65536 KB	Execution killed with signal 9
88	Runtime error	111 ms	65536 KB	Execution killed with signal 9
89	Runtime error	114 ms	65536 KB	Execution killed with signal 9
90	Runtime error	112 ms	65536 KB	Execution killed with signal 9
91	Runtime error	112 ms	65536 KB	Execution killed with signal 9
92	Runtime error	116 ms	65536 KB	Execution killed with signal 9