답안 #98202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98202	2019-02-21T13:43:35 Z	SuperJava	Mecho (IOI09_mecho)	C++17	100 / 100	535 ms	6132 KB

mecho

//fold
#ifndef KHALIL
#include <bits/stdc++.h>
#else
#include "header.h"
#endif
#define endl '\n'
#define mp make_pair
#define tostr(x) static_cast<ostringstream&>((ostringstream()<<dec<<x)).str()
#define rep(i,begin,end) for(auto i = begin;i < end;i++)
#define repr(i,begin,end) for(auto i = begin-1;i >= end;i--)
#define pb push_back
#define sz(a) ((int)(a).size())
#define fi first
#define se second
#define abs(a) ((a) < (0) ? (-1)*(a) : (a))
#define SQ(a) ((a)*(a))
#define eqd(a,b) (abs(a-b)<1e-9)
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename t> t in(t q){cin >> q;return q;}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v){os << "[";for (int i = 0; i < sz(v); ++i) { os << v[i]; if (i != sz(v) - 1) os << ",";}os << "]";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const map<T, S>& v){for (auto it : v)os << "(" << it.first << ":" << it.second << ")";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const pair<T, S>& v){os << "(" << v.first << "," << v.second << ")";return os;}
const long double PI = acosl(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng);}
//endfold
#define  N  (805)
#define MOD (1000000000l + 7l)
#define OO (1050000000)
#define OOL (1100000000000000000)
 
int b[N][N];
int z[N][N];
int n,s;
 
int dr[4] = {1,-1,0,0};
int dc[4] = {0,0,1,-1};
 
pair<int,int> target;
queue<pair<pair<int,int>,int>> q;
queue<pair<pair<int,int>,int>> q1;
 
void reset(){
	while(!q.empty()) q.pop();
	while(!q1.empty()) q1.pop();
	rep(i,0,n){
		rep(j,0,n){
			z[i][j] = b[i][j];
			if(z[i][j] == 1) q1.push({{i,j},0});
			if(z[i][j] == 2) q.push({{i,j},0});
		}
	}
}
 
void simulate(int steps){
	if(steps == 0) return;
	while(!q1.empty()){
		if(q1.front().second == steps) break;
		auto t = q1.front(); q1.pop();
		int r = t.first.first;
		int c = t.first.second;
		rep(i,0,4){
			int nr = r+dr[i];
			int nc = c+dc[i];
			if(nr >= 0 && nr < n && nc >= 0 && nc < n){
				if(z[nr][nc] != -1 && z[nr][nc] != 1 && !(nr == target.first && nc == target.second)){
					z[nr][nc] = 1;
					q1.push({{nr,nc},t.second+1});
				}
			}
		}
	}
}
 
int simulate2(int steps){
	if(q.size() == 0) return -1;
	while(!q.empty()){
		if(q.front().second == steps) break;
		auto t = q.front(); q.pop();
		int r = t.first.first;
		int c = t.first.second;
		if(z[r][c] != 2) continue;
		rep(i,0,4){
			int nr = r+dr[i];
			int nc = c+dc[i];
			if(nr >= 0 && nr < n && nc >= 0 && nc < n){
				if(z[nr][nc] == 0){
					z[nr][nc] = 2;
					q.push({{nr,nc},t.second+1});
				}
			}
		}
	}
	return 1;
}
 
int main(){
	//fold
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cout << setprecision(10);
	//endfold
	cin >> n >> s;
	rep(i,0,n){
		string q;
		cin >> q;
		rep(j,0,n){
			if(q[j] == 'D') target = {i,j};
			if(q[j] == 'T') b[i][j] = -1;
			if(q[j] == 'H') b[i][j] = 1;
			if(q[j] == 'M') b[i][j] = 2;
		}
	}
	int l = 0,r = n*n/2,best = -1;
	while(l <= r){
		int mid = (l+r)/2;
		reset();
		int we = mid;
		int ew = s;
		simulate(we++);
		bool good = false;
		while(simulate2(ew) > 0){
			if(z[target.first][target.second] == 2){
				good = true;
				break;
			}
			ew += s;
			simulate(we++);
		}
		if(good){
			best = mid;
			l = mid+1;
		}else{
			r = mid-1;
		}
	}
	cout << best;
	return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	416 KB	Output is correct
7	Correct	404 ms	4860 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	484 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	2 ms	740 KB	Output is correct
13	Correct	3 ms	640 KB	Output is correct
14	Correct	4 ms	768 KB	Output is correct
15	Correct	2 ms	512 KB	Output is correct
16	Correct	2 ms	512 KB	Output is correct
17	Correct	3 ms	512 KB	Output is correct
18	Correct	3 ms	512 KB	Output is correct
19	Correct	3 ms	512 KB	Output is correct
20	Correct	0 ms	512 KB	Output is correct
21	Correct	2 ms	512 KB	Output is correct
22	Correct	3 ms	640 KB	Output is correct
23	Correct	4 ms	660 KB	Output is correct
24	Correct	3 ms	640 KB	Output is correct
25	Correct	3 ms	640 KB	Output is correct
26	Correct	4 ms	768 KB	Output is correct
27	Correct	3 ms	768 KB	Output is correct
28	Correct	3 ms	768 KB	Output is correct
29	Correct	4 ms	768 KB	Output is correct
30	Correct	3 ms	768 KB	Output is correct
31	Correct	4 ms	768 KB	Output is correct
32	Correct	3 ms	768 KB	Output is correct
33	Correct	28 ms	2432 KB	Output is correct
34	Correct	29 ms	2560 KB	Output is correct
35	Correct	50 ms	2616 KB	Output is correct
36	Correct	37 ms	2736 KB	Output is correct
37	Correct	40 ms	2920 KB	Output is correct
38	Correct	53 ms	2816 KB	Output is correct
39	Correct	63 ms	3192 KB	Output is correct
40	Correct	68 ms	3200 KB	Output is correct
41	Correct	113 ms	3200 KB	Output is correct
42	Correct	65 ms	3484 KB	Output is correct
43	Correct	68 ms	3584 KB	Output is correct
44	Correct	145 ms	3556 KB	Output is correct
45	Correct	98 ms	3832 KB	Output is correct
46	Correct	102 ms	3868 KB	Output is correct
47	Correct	155 ms	3876 KB	Output is correct
48	Correct	112 ms	4216 KB	Output is correct
49	Correct	108 ms	4188 KB	Output is correct
50	Correct	186 ms	4224 KB	Output is correct
51	Correct	115 ms	4480 KB	Output is correct
52	Correct	112 ms	4480 KB	Output is correct
53	Correct	177 ms	4508 KB	Output is correct
54	Correct	155 ms	4820 KB	Output is correct
55	Correct	147 ms	4816 KB	Output is correct
56	Correct	246 ms	4856 KB	Output is correct
57	Correct	182 ms	5100 KB	Output is correct
58	Correct	178 ms	5256 KB	Output is correct
59	Correct	314 ms	5288 KB	Output is correct
60	Correct	208 ms	5564 KB	Output is correct
61	Correct	167 ms	5576 KB	Output is correct
62	Correct	288 ms	5576 KB	Output is correct
63	Correct	305 ms	5572 KB	Output is correct
64	Correct	386 ms	5628 KB	Output is correct
65	Correct	318 ms	5568 KB	Output is correct
66	Correct	355 ms	5624 KB	Output is correct
67	Correct	334 ms	5568 KB	Output is correct
68	Correct	339 ms	5632 KB	Output is correct
69	Correct	390 ms	5496 KB	Output is correct
70	Correct	377 ms	5616 KB	Output is correct
71	Correct	411 ms	5612 KB	Output is correct
72	Correct	439 ms	5616 KB	Output is correct
73	Correct	372 ms	6008 KB	Output is correct
74	Correct	399 ms	5880 KB	Output is correct
75	Correct	458 ms	5988 KB	Output is correct
76	Correct	425 ms	5980 KB	Output is correct
77	Correct	510 ms	5992 KB	Output is correct
78	Correct	439 ms	5888 KB	Output is correct
79	Correct	407 ms	5940 KB	Output is correct
80	Correct	454 ms	5936 KB	Output is correct
81	Correct	427 ms	5944 KB	Output is correct
82	Correct	399 ms	5940 KB	Output is correct
83	Correct	418 ms	6132 KB	Output is correct
84	Correct	489 ms	6016 KB	Output is correct
85	Correct	468 ms	5992 KB	Output is correct
86	Correct	491 ms	6008 KB	Output is correct
87	Correct	418 ms	5976 KB	Output is correct
88	Correct	428 ms	5760 KB	Output is correct
89	Correct	447 ms	5760 KB	Output is correct
90	Correct	426 ms	5760 KB	Output is correct
91	Correct	381 ms	5880 KB	Output is correct
92	Correct	535 ms	5808 KB	Output is correct