답안 #97900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97900	2019-02-19T12:50:06 Z	SuperJava	Mecho (IOI09_mecho)	C++17	11 / 100	1000 ms	14152 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};

void reset(){
	rep(i,0,n){
		rep(j,0,n){
			z[i][j] = b[i][j];
		}
	}
}

void simulate(int steps){
	if(steps == 0) return;
	queue<pair<pair<int,int>,int>> q;
	rep(i,0,n){
		rep(j,0,n){
			if(z[i][j] == 1){
				q.push({{i,j},0});
			}
		}
	}
	while(!q.empty()){
		auto t = q.front(); q.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){
					z[nr][nc] = 1;
					if(t.second != steps-1){
						q.push({{nr,nc},t.second+1});
					}
				}
			}
		}
	}
}

int simulate2(int steps){
	queue<pair<pair<int,int>,int>> q;
	rep(i,0,n){
		rep(j,0,n){
			if(z[i][j] == 2){
				q.push({{i,j},0});
			}
		}
	}
	if(q.size() == 0) return -1;
	while(!q.empty()){
		auto t = q.front(); q.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] == 0){
					z[nr][nc] = 2;
					if(t.second != steps-1){
						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
	pair<int,int> target;
	cin >> n >> s;
	rep(i,0,n){
		string q;
		cin >> q;
		map<char,int> pw = {{'T',-1},{'G',0},
					{'H',1},{'M',2},{'D',0}};
		rep(j,0,n){
			if(q[j] == 'D') target = {i,j};
			b[i][j] = pw[q[j]];
		}
	}
	int l = 1,r = 2*n,best = -1;
	while(l <= r){
		int mid = (l+r)/2;
		reset();
		simulate(mid);
		bool good = false;
		while(simulate2(s) > 0){
			if(z[target.first][target.second] == 2){
				good = true;
				break;
			}
			simulate(1);
		}
		if(good){
			best = mid;
			l = mid+1;
		}else{
			r = mid-1;
		}
	}
	cout << best;
	return 0;
}

Subtask #1

11.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Incorrect	2 ms	384 KB	Output isn't correct
3	Correct	2 ms	384 KB	Output is correct
4	Incorrect	2 ms	384 KB	Output isn't correct
5	Incorrect	2 ms	384 KB	Output isn't correct
6	Incorrect	3 ms	384 KB	Output isn't correct
7	Execution timed out	1075 ms	13948 KB	Time limit exceeded
8	Correct	3 ms	384 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Incorrect	7 ms	768 KB	Output isn't correct
13	Incorrect	3 ms	640 KB	Output isn't correct
14	Correct	6 ms	768 KB	Output is correct
15	Incorrect	2 ms	512 KB	Output isn't correct
16	Incorrect	2 ms	512 KB	Output isn't correct
17	Incorrect	2 ms	512 KB	Output isn't correct
18	Incorrect	3 ms	512 KB	Output isn't correct
19	Incorrect	3 ms	512 KB	Output isn't correct
20	Incorrect	3 ms	572 KB	Output isn't correct
21	Incorrect	2 ms	640 KB	Output isn't correct
22	Incorrect	3 ms	640 KB	Output isn't correct
23	Incorrect	3 ms	640 KB	Output isn't correct
24	Incorrect	3 ms	640 KB	Output isn't correct
25	Incorrect	4 ms	768 KB	Output isn't correct
26	Incorrect	4 ms	768 KB	Output isn't correct
27	Incorrect	2 ms	768 KB	Output isn't correct
28	Incorrect	4 ms	768 KB	Output isn't correct
29	Incorrect	3 ms	768 KB	Output isn't correct
30	Incorrect	3 ms	768 KB	Output isn't correct
31	Incorrect	3 ms	768 KB	Output isn't correct
32	Incorrect	4 ms	896 KB	Output isn't correct
33	Incorrect	10 ms	2688 KB	Output isn't correct
34	Incorrect	11 ms	2688 KB	Output isn't correct
35	Execution timed out	1068 ms	4128 KB	Time limit exceeded
36	Incorrect	12 ms	3072 KB	Output isn't correct
37	Incorrect	13 ms	3072 KB	Output isn't correct
38	Execution timed out	1068 ms	4776 KB	Time limit exceeded
39	Incorrect	14 ms	3456 KB	Output isn't correct
40	Incorrect	14 ms	3456 KB	Output isn't correct
41	Execution timed out	1071 ms	5296 KB	Time limit exceeded
42	Incorrect	21 ms	3840 KB	Output isn't correct
43	Incorrect	19 ms	3840 KB	Output isn't correct
44	Execution timed out	1075 ms	5964 KB	Time limit exceeded
45	Incorrect	26 ms	4224 KB	Output isn't correct
46	Incorrect	23 ms	4224 KB	Output isn't correct
47	Execution timed out	1074 ms	6420 KB	Time limit exceeded
48	Incorrect	23 ms	4480 KB	Output isn't correct
49	Incorrect	24 ms	4480 KB	Output isn't correct
50	Execution timed out	1056 ms	6948 KB	Time limit exceeded
51	Incorrect	37 ms	4984 KB	Output isn't correct
52	Incorrect	37 ms	4864 KB	Output isn't correct
53	Execution timed out	1082 ms	7180 KB	Time limit exceeded
54	Incorrect	30 ms	5248 KB	Output isn't correct
55	Incorrect	35 ms	5376 KB	Output isn't correct
56	Execution timed out	1082 ms	7820 KB	Time limit exceeded
57	Incorrect	30 ms	5632 KB	Output isn't correct
58	Incorrect	39 ms	5632 KB	Output isn't correct
59	Execution timed out	1073 ms	8408 KB	Time limit exceeded
60	Incorrect	39 ms	6072 KB	Output isn't correct
61	Incorrect	40 ms	6116 KB	Output isn't correct
62	Execution timed out	1068 ms	9028 KB	Time limit exceeded
63	Execution timed out	1043 ms	7508 KB	Time limit exceeded
64	Execution timed out	1081 ms	9312 KB	Time limit exceeded
65	Execution timed out	1035 ms	6848 KB	Time limit exceeded
66	Execution timed out	1072 ms	7636 KB	Time limit exceeded
67	Execution timed out	1081 ms	7372 KB	Time limit exceeded
68	Execution timed out	1069 ms	10540 KB	Time limit exceeded
69	Execution timed out	1066 ms	10564 KB	Time limit exceeded
70	Execution timed out	1067 ms	10352 KB	Time limit exceeded
71	Execution timed out	1059 ms	10580 KB	Time limit exceeded
72	Correct	320 ms	10652 KB	Output is correct
73	Execution timed out	1075 ms	10540 KB	Time limit exceeded
74	Execution timed out	1057 ms	13868 KB	Time limit exceeded
75	Execution timed out	1064 ms	13644 KB	Time limit exceeded
76	Execution timed out	1066 ms	13848 KB	Time limit exceeded
77	Execution timed out	1061 ms	13900 KB	Time limit exceeded
78	Execution timed out	1030 ms	14152 KB	Time limit exceeded
79	Execution timed out	1063 ms	13808 KB	Time limit exceeded
80	Execution timed out	1012 ms	12976 KB	Time limit exceeded
81	Execution timed out	1030 ms	13880 KB	Time limit exceeded
82	Execution timed out	1042 ms	13956 KB	Time limit exceeded
83	Execution timed out	1054 ms	13980 KB	Time limit exceeded
84	Execution timed out	1069 ms	13804 KB	Time limit exceeded
85	Execution timed out	1059 ms	12208 KB	Time limit exceeded
86	Execution timed out	1049 ms	13880 KB	Time limit exceeded
87	Execution timed out	1060 ms	13920 KB	Time limit exceeded
88	Execution timed out	1038 ms	14036 KB	Time limit exceeded
89	Execution timed out	1046 ms	13116 KB	Time limit exceeded
90	Execution timed out	1020 ms	13992 KB	Time limit exceeded
91	Execution timed out	1042 ms	14056 KB	Time limit exceeded
92	Execution timed out	1063 ms	14072 KB	Time limit exceeded