답안 #757231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757231	2023-06-12T20:24:30 Z	shadow_sami	Mecho (IOI09_mecho)	C++17	100 / 100	808 ms	11832 KB

mecho

#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;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 800+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
char c[mx][mx];
queue<pi> q;
ll dx[4] = {1,0,-1,0};
ll dy[4] = {0,1,0,-1};
pi pos,house;
vector<pi> v;
ll vis[mx][mx];
ll vis2[mx][mx];

bool ok(ll x,ll y){
	return (x >= 0 && x < n && y >= 0 && y < n && vis[x][y] == -1 && (c[x][y] == 'M' || c[x][y] == 'G'));
}

bool ok2(ll x,ll y){
	return (x >= 0 && x < n && y >= 0 && y < n && vis2[x][y] == -1 && (c[x][y] == 'M' || c[x][y] == 'G'));
}

void emptify(){
	while(q.size())
		q.pop();
	return;
}

bool meow(ll k){
	fip(0,n+2)
		fjp(0,n+2){
			vis2[i][j] = -1;
			vis[i][j] = -1;
		}
	emptify();
	fx(v){
		vis[x.ff][x.ss] = 0;
		q.push({x.ff,x.ss});
	}
	while(q.size()){
		pi x = q.front();
		// debug(x);
		q.pop();
		fip(0,4){
			if(ok(x.ff+dx[i],x.ss+dy[i])){
				vis[x.ff+dx[i]][x.ss+dy[i]] = vis[x.ff][x.ss] + 1;
				q.push({x.ff+dx[i],x.ss+dy[i]});
			}
		}
	}
	emptify();
	q.push(pos);
	vis2[pos.ff][pos.ss] = 0;
	if(vis[pos.ff][pos.ss] <= k)
		q.pop();
	while(q.size()){
		auto x = q.front();
		q.pop();
		fip(0,4) 
			if(ok2(x.ff+dx[i],x.ss+dy[i])){
				if(((vis2[x.ff][x.ss] + 1) / m) + k >= vis[x.ff+dx[i]][x.ss+dy[i]])
					continue;
				vis2[x.ff+dx[i]][x.ss+dy[i]] = (vis2[x.ff][x.ss] + 1) ;
				q.push({x.ff+dx[i],x.ss+dy[i]});
			}
	}
	// fip(0,n){
	// 	fjp(0,n){
	// 		cout<<vis[i][j];
	// 	}
	// 	cout<<nli;
	// }
	fip(0,n)
		fjp(0,n){
			if(-1 != vis2[i][j])
				vis2[i][j]/=m;
		}
	// fip(0,n){
	// 	fjp(0,n){
	// 		cout<<vis2[i][j];
	// 	}
	// 	cout<<nli;
	// }
	f = 0;
	fip(0,4)
		if(house.ff + dx[i] >= 0 && house.ff + dx[i] < n && house.ss + dy[i] >= 0 && house.ss + dy[i] < n && c[house.ff+dx[i]][house.ss+dy[i]] != 'T'){
			if(vis2[house.ff+dx[i]][house.ss+dy[i]] != -1 && vis2[house.ff + dx[i]][house.ss + dy[i]] + k < vis[house.ff + dx[i]][house.ss + dy[i]]){				
				f = 1;
			}
		}	
	return f;
}

ll l,r,mid;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n>>m;
        ans = -1;        
        fip(0,n)
        	fjp(0,n){
        		cin>>c[i][j];
        		if(c[i][j]=='H')
        			v.push_back({i,j});
        		else if(c[i][j]=='M')
        			pos = {i,j};
        		else if(c[i][j]=='D')
        			house = {i,j};
        	}
        // cout<<meow(3)<<nli;
        l = 0,r = 1e9;
        while(l<=r){
        	mid = l + (r-l)/2;
        	if(meow(mid)){
        		ans = mid;
        		l = mid + 1;
        	}else
        		r = mid - 1;
        }
        cout<<ans<<nli;
        
    cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	651 ms	11288 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	2 ms	952 KB	Output is correct
13	Correct	4 ms	852 KB	Output is correct
14	Correct	4 ms	852 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	1 ms	468 KB	Output is correct
17	Correct	1 ms	468 KB	Output is correct
18	Correct	1 ms	596 KB	Output is correct
19	Correct	1 ms	596 KB	Output is correct
20	Correct	1 ms	596 KB	Output is correct
21	Correct	1 ms	724 KB	Output is correct
22	Correct	1 ms	724 KB	Output is correct
23	Correct	2 ms	852 KB	Output is correct
24	Correct	2 ms	852 KB	Output is correct
25	Correct	2 ms	852 KB	Output is correct
26	Correct	2 ms	852 KB	Output is correct
27	Correct	3 ms	980 KB	Output is correct
28	Correct	2 ms	980 KB	Output is correct
29	Correct	3 ms	980 KB	Output is correct
30	Correct	3 ms	980 KB	Output is correct
31	Correct	5 ms	1116 KB	Output is correct
32	Correct	3 ms	1108 KB	Output is correct
33	Correct	66 ms	5032 KB	Output is correct
34	Correct	50 ms	4948 KB	Output is correct
35	Correct	96 ms	5036 KB	Output is correct
36	Correct	67 ms	5716 KB	Output is correct
37	Correct	71 ms	5716 KB	Output is correct
38	Correct	150 ms	5728 KB	Output is correct
39	Correct	88 ms	6388 KB	Output is correct
40	Correct	85 ms	6356 KB	Output is correct
41	Correct	212 ms	6424 KB	Output is correct
42	Correct	107 ms	7040 KB	Output is correct
43	Correct	101 ms	7044 KB	Output is correct
44	Correct	225 ms	7060 KB	Output is correct
45	Correct	137 ms	7756 KB	Output is correct
46	Correct	119 ms	7716 KB	Output is correct
47	Correct	242 ms	7736 KB	Output is correct
48	Correct	170 ms	8376 KB	Output is correct
49	Correct	157 ms	8376 KB	Output is correct
50	Correct	327 ms	8404 KB	Output is correct
51	Correct	221 ms	9044 KB	Output is correct
52	Correct	184 ms	9064 KB	Output is correct
53	Correct	390 ms	9076 KB	Output is correct
54	Correct	247 ms	9712 KB	Output is correct
55	Correct	226 ms	9712 KB	Output is correct
56	Correct	503 ms	9732 KB	Output is correct
57	Correct	260 ms	10388 KB	Output is correct
58	Correct	237 ms	10404 KB	Output is correct
59	Correct	631 ms	10420 KB	Output is correct
60	Correct	282 ms	11052 KB	Output is correct
61	Correct	322 ms	11056 KB	Output is correct
62	Correct	637 ms	11068 KB	Output is correct
63	Correct	722 ms	11072 KB	Output is correct
64	Correct	808 ms	11092 KB	Output is correct
65	Correct	734 ms	11084 KB	Output is correct
66	Correct	684 ms	11064 KB	Output is correct
67	Correct	661 ms	11072 KB	Output is correct
68	Correct	662 ms	11128 KB	Output is correct
69	Correct	688 ms	11128 KB	Output is correct
70	Correct	641 ms	11140 KB	Output is correct
71	Correct	633 ms	11128 KB	Output is correct
72	Correct	624 ms	11128 KB	Output is correct
73	Correct	601 ms	11800 KB	Output is correct
74	Correct	721 ms	11764 KB	Output is correct
75	Correct	628 ms	11820 KB	Output is correct
76	Correct	649 ms	11736 KB	Output is correct
77	Correct	650 ms	11748 KB	Output is correct
78	Correct	646 ms	11728 KB	Output is correct
79	Correct	668 ms	11604 KB	Output is correct
80	Correct	677 ms	11604 KB	Output is correct
81	Correct	681 ms	11832 KB	Output is correct
82	Correct	668 ms	11592 KB	Output is correct
83	Correct	634 ms	11512 KB	Output is correct
84	Correct	624 ms	11516 KB	Output is correct
85	Correct	681 ms	11528 KB	Output is correct
86	Correct	690 ms	11516 KB	Output is correct
87	Correct	670 ms	11516 KB	Output is correct
88	Correct	661 ms	11468 KB	Output is correct
89	Correct	634 ms	11400 KB	Output is correct
90	Correct	642 ms	11400 KB	Output is correct
91	Correct	640 ms	11400 KB	Output is correct
92	Correct	665 ms	11424 KB	Output is correct