Submission #742717

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742717	2023-05-16T18:51:25 Z	airths	Mecho (IOI09_mecho)	C++17	27 / 100	580 ms	16688 KB

mecho

/*
 * 
 * 	^v^
 * 
 */
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <iomanip>
#include <map>
#include <numeric>
#include <functional>
#include <algorithm>
#include <set>
#include <queue>
#include <climits>
#include <cstdlib>
#include <chrono>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define iamtefu ios_base::sync_with_stdio(false); cin.tie(0);
#define ll long long int
#define ld long double
#define sc(a) scanf("%lld", &a);
#define scv(a, n) vector<ll> a(n);fl(i,0,n){sc(a[i])}
#define prl(a) fl(i,0,a.size()){printf("%lld ", a[i]);}printf("\n");
#define fl(i,a,n) for (ll i(a); i<n; i++)
#define rfl(i,a,n) for (ll i(n-1); i>=a; i--)
#define print(a) for (auto x:a){cout<<x<<" ";} cout<<"\n";
#define tt int tt; cin>>tt; for(;tt--;)
ll gcd(ll a, ll b){
	if (b==0){
		return a;
	}
	return gcd(b, a%b);
}
ll pw(ll a, ll b, ll m){
	ll res=1;
	a%=m;
	while (b){
		if (b&1){
			res=(res*a)%m;
		}
		a=(a*a)%m;
		b/=2;
	}
	return res;
}
void scn(){
	ll n, s; cin>>n>>s;
	vector <string> c(n);
	vector <vector <ll>> a(n+1, vector <ll>(n+1, 1e9));
	queue <vector <ll>> q;
	fl(i,0,n){
		cin>>c[i];
		fl(j,0,n){
			if (c[i][j]=='H'){
				q.push({i, j});
				a[i][j]=0;
			}
		}
	}
	vector <ll> di={1, 1, 0, -1, -1, -1, 0, 1};
	vector <ll> dj={0, 1, 1, 1, 0, -1, -1, -1};
	while (!q.empty()){
		auto j = q.front();
		q.pop();
		for (int d=0; d<8; d+=2){
			ll i1 = j[0]+di[d], j1 = j[1]+dj[d];
			if (i1>=0 && j1>=0 && i1<n && j1<n && a[i1][j1]==1e9 && (c[i1][j1]=='G' || c[i1][j1]=='M')){
				q.push({i1, j1});
				a[i1][j1]=a[j[0]][j[1]]+1;
			}
		}
	}
	vector <vector <ll>> dis(n+1, vector <ll>(n+1, 1e9));
	vector <ll> hij;
	fl(i,0,n){
		fl(j,0,n){
			if (c[i][j]=='M'){
				q.push({i, j});
				dis[i][j]=0;
				hij={i, j};
			}
		}
	}
	while (!q.empty()){
		auto j = q.front();
		q.pop();
		for (int d=0; d<8; d+=2){
			ll i1 = j[0]+di[d], j1 = j[1]+dj[d];
			if (i1>=0 && j1>=0 && i1<n && j1<n && dis[i1][j1]==1e9 && (c[i1][j1]=='G' || c[i1][j1]=='D')){
				dis[i1][j1]=dis[j[0]][j[1]]+1;
				q.push({i1, j1});
			}
		}
	}
	for (auto &y:dis){
		for (auto &x:y){
			if (x!=1e9){
				x=(x+s-1)/s;
			}
		}
	}
	if (a[hij[0]][hij[1]]==0){
		cout<<"-1\n";
		return;
	}
	// for (auto x:dis){
	// 	print(x)
	// }
	// cout<<'\n';
	// for (auto x:a){
	// 	print(x)
	// }
	auto ist=[&](ll mid){
		vector <vector <ll>> vis(n+1, vector <ll>(n+1));
		queue <vector <ll>> q;
		q.push({hij[0], hij[1], s});
		while (!q.empty()){
			auto j = q.front();
			q.pop();
			if (c[j[0]][j[1]]=='D'){
				return true;
			}
			if (j[2]==0 && dis[j[0]][j[1]]+mid>=a[j[0]][j[1]]){
				// cout<<dis[j[0]][j[1]]<<" "<<mid<<" "<<a[j[0]][j[1]]<<"  pl1\n";
				continue;
			} else if (j[2] && dis[j[0]][j[1]]+mid>=a[j[0]][j[1]]){
				continue;
			}
			// cout<<c[j[0]][j[1]]<<"  pl\n";
			for (int d=0; d<8; d+=2){
				ll i1 = j[0]+di[d], j1 = j[1]+dj[d];
				if (i1>=0 && i1<n && j1>=0 && j1<n && (c[i1][j1]=='D' || c[i1][j1]=='G') && vis[i1][j1]==0){
					q.push({i1, j1, (j[2]==0?s-1:j[2]-1)});
					vis[i1][j1]++;
				}
			}
		}
		return false;
	};
	ll l = 0, r = 1e18;
	// cout<<ist(3)<<"  o\n";
	while (l<=r){
		// cout<<l<<" "<<r<<'\n';
		ll mid = (l+r)/2;
		// cout<<mid<<" "<<ist(mid)<<"  pl\n";
		if (ist(mid)){
			l = mid+1;
		} else {
			r = mid-1;
		}
	}
	if (ist(0)==0){
		cout<<"-1\n";
		return;
	}
	cout<<max(0ll,l-1)<<'\n';

	// not necessarily distinct
}
int main(){
	iamtefu;
#if defined(airths)
	auto t1=chrono::high_resolution_clock::now();
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//
#endif
	// tt
	{
		scn();
	}
#if defined(airths)
	auto t2=chrono::high_resolution_clock::now();
	ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count();
	ti*=1e-6;
	cerr<<"Time: "<<setprecision(12)<<ti;
	cerr<<"ms\n";
#endif
	return 0;
}

Subtask #1

27.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Incorrect	0 ms	212 KB	Output isn't correct
6	Incorrect	0 ms	212 KB	Output isn't correct
7	Incorrect	424 ms	16432 KB	Output isn't correct
8	Correct	0 ms	212 KB	Output is correct
9	Incorrect	1 ms	212 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	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	340 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Incorrect	0 ms	212 KB	Output isn't correct
17	Correct	1 ms	340 KB	Output is correct
18	Incorrect	1 ms	340 KB	Output isn't correct
19	Correct	1 ms	340 KB	Output is correct
20	Incorrect	1 ms	340 KB	Output isn't correct
21	Correct	1 ms	340 KB	Output is correct
22	Incorrect	1 ms	340 KB	Output isn't correct
23	Correct	1 ms	340 KB	Output is correct
24	Incorrect	1 ms	340 KB	Output isn't correct
25	Correct	1 ms	340 KB	Output is correct
26	Incorrect	1 ms	340 KB	Output isn't correct
27	Correct	1 ms	340 KB	Output is correct
28	Incorrect	1 ms	340 KB	Output isn't correct
29	Correct	1 ms	340 KB	Output is correct
30	Incorrect	1 ms	340 KB	Output isn't correct
31	Correct	1 ms	468 KB	Output is correct
32	Incorrect	1 ms	468 KB	Output isn't correct
33	Correct	25 ms	3384 KB	Output is correct
34	Incorrect	27 ms	3580 KB	Output isn't correct
35	Correct	79 ms	3384 KB	Output is correct
36	Correct	44 ms	4300 KB	Output is correct
37	Incorrect	36 ms	4472 KB	Output isn't correct
38	Correct	101 ms	4332 KB	Output is correct
39	Correct	47 ms	5564 KB	Output is correct
40	Incorrect	47 ms	5572 KB	Output isn't correct
41	Correct	146 ms	5556 KB	Output is correct
42	Correct	56 ms	6520 KB	Output is correct
43	Incorrect	53 ms	6716 KB	Output isn't correct
44	Correct	169 ms	6684 KB	Output is correct
45	Correct	61 ms	7984 KB	Output is correct
46	Incorrect	71 ms	7940 KB	Output isn't correct
47	Correct	194 ms	8096 KB	Output is correct
48	Correct	75 ms	9592 KB	Output is correct
49	Incorrect	76 ms	9600 KB	Output isn't correct
50	Correct	260 ms	9588 KB	Output is correct
51	Correct	93 ms	10876 KB	Output is correct
52	Incorrect	102 ms	10908 KB	Output isn't correct
53	Correct	299 ms	10984 KB	Output is correct
54	Correct	104 ms	12612 KB	Output is correct
55	Incorrect	110 ms	12596 KB	Output isn't correct
56	Correct	359 ms	12564 KB	Output is correct
57	Correct	124 ms	14380 KB	Output is correct
58	Incorrect	129 ms	14428 KB	Output isn't correct
59	Correct	406 ms	14524 KB	Output is correct
60	Correct	141 ms	16284 KB	Output is correct
61	Incorrect	143 ms	16520 KB	Output isn't correct
62	Correct	471 ms	16328 KB	Output is correct
63	Incorrect	358 ms	16268 KB	Output isn't correct
64	Incorrect	580 ms	16376 KB	Output isn't correct
65	Incorrect	579 ms	16436 KB	Output isn't correct
66	Correct	457 ms	16296 KB	Output is correct
67	Correct	388 ms	16348 KB	Output is correct
68	Incorrect	224 ms	16364 KB	Output isn't correct
69	Incorrect	250 ms	16320 KB	Output isn't correct
70	Incorrect	198 ms	16444 KB	Output isn't correct
71	Incorrect	204 ms	16356 KB	Output isn't correct
72	Correct	205 ms	16448 KB	Output is correct
73	Correct	259 ms	16536 KB	Output is correct
74	Incorrect	346 ms	16508 KB	Output isn't correct
75	Incorrect	342 ms	16640 KB	Output isn't correct
76	Incorrect	306 ms	16532 KB	Output isn't correct
77	Incorrect	336 ms	16688 KB	Output isn't correct
78	Correct	353 ms	16460 KB	Output is correct
79	Incorrect	334 ms	16556 KB	Output isn't correct
80	Incorrect	322 ms	16564 KB	Output isn't correct
81	Incorrect	342 ms	16480 KB	Output isn't correct
82	Incorrect	326 ms	16428 KB	Output isn't correct
83	Incorrect	365 ms	16488 KB	Output isn't correct
84	Incorrect	389 ms	16504 KB	Output isn't correct
85	Incorrect	354 ms	16416 KB	Output isn't correct
86	Incorrect	406 ms	16428 KB	Output isn't correct
87	Incorrect	372 ms	16420 KB	Output isn't correct
88	Incorrect	371 ms	16380 KB	Output isn't correct
89	Incorrect	421 ms	16468 KB	Output isn't correct
90	Incorrect	409 ms	16412 KB	Output isn't correct
91	Incorrect	415 ms	16372 KB	Output isn't correct
92	Incorrect	403 ms	16504 KB	Output isn't correct