Submission #742712

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742712	2023-05-16T18:44:20 Z	airths	Mecho (IOI09_mecho)	C++17	39 / 100	516 ms	16780 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-1>=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 = n+1;
	// 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

39.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	337 ms	16492 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Incorrect	1 ms	340 KB	Output isn't correct
13	Incorrect	2 ms	340 KB	Output isn't correct
14	Correct	1 ms	340 KB	Output is correct
15	Incorrect	0 ms	212 KB	Output isn't correct
16	Incorrect	1 ms	212 KB	Output isn't correct
17	Incorrect	1 ms	340 KB	Output isn't correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Incorrect	1 ms	340 KB	Output isn't correct
20	Incorrect	0 ms	340 KB	Output isn't correct
21	Incorrect	0 ms	340 KB	Output isn't correct
22	Incorrect	1 ms	340 KB	Output isn't correct
23	Incorrect	1 ms	340 KB	Output isn't correct
24	Incorrect	1 ms	340 KB	Output isn't correct
25	Incorrect	1 ms	340 KB	Output isn't correct
26	Incorrect	1 ms	340 KB	Output isn't correct
27	Incorrect	1 ms	340 KB	Output isn't correct
28	Incorrect	1 ms	340 KB	Output isn't correct
29	Incorrect	1 ms	340 KB	Output isn't correct
30	Incorrect	1 ms	340 KB	Output isn't correct
31	Incorrect	1 ms	468 KB	Output isn't correct
32	Incorrect	1 ms	456 KB	Output isn't correct
33	Incorrect	16 ms	3412 KB	Output isn't correct
34	Incorrect	13 ms	3544 KB	Output isn't correct
35	Incorrect	69 ms	3500 KB	Output isn't correct
36	Incorrect	19 ms	4256 KB	Output isn't correct
37	Incorrect	19 ms	4404 KB	Output isn't correct
38	Incorrect	83 ms	4452 KB	Output isn't correct
39	Incorrect	20 ms	5412 KB	Output isn't correct
40	Incorrect	21 ms	5516 KB	Output isn't correct
41	Incorrect	113 ms	5624 KB	Output isn't correct
42	Incorrect	27 ms	6544 KB	Output isn't correct
43	Incorrect	27 ms	6640 KB	Output isn't correct
44	Incorrect	133 ms	6732 KB	Output isn't correct
45	Incorrect	30 ms	7840 KB	Output isn't correct
46	Incorrect	35 ms	8056 KB	Output isn't correct
47	Incorrect	174 ms	7996 KB	Output isn't correct
48	Incorrect	35 ms	9268 KB	Output isn't correct
49	Incorrect	38 ms	9636 KB	Output isn't correct
50	Incorrect	204 ms	9516 KB	Output isn't correct
51	Incorrect	50 ms	10840 KB	Output isn't correct
52	Incorrect	44 ms	11104 KB	Output isn't correct
53	Incorrect	252 ms	11080 KB	Output isn't correct
54	Incorrect	50 ms	12496 KB	Output isn't correct
55	Incorrect	54 ms	12760 KB	Output isn't correct
56	Incorrect	285 ms	12744 KB	Output isn't correct
57	Incorrect	65 ms	14356 KB	Output isn't correct
58	Incorrect	59 ms	14544 KB	Output isn't correct
59	Incorrect	360 ms	14532 KB	Output isn't correct
60	Incorrect	64 ms	16196 KB	Output isn't correct
61	Incorrect	77 ms	16468 KB	Output isn't correct
62	Incorrect	398 ms	16428 KB	Output isn't correct
63	Correct	346 ms	16284 KB	Output is correct
64	Incorrect	516 ms	16472 KB	Output isn't correct
65	Correct	422 ms	16248 KB	Output is correct
66	Correct	340 ms	16168 KB	Output is correct
67	Correct	316 ms	16160 KB	Output is correct
68	Correct	178 ms	16476 KB	Output is correct
69	Correct	154 ms	16488 KB	Output is correct
70	Correct	141 ms	16484 KB	Output is correct
71	Correct	137 ms	16300 KB	Output is correct
72	Incorrect	111 ms	16504 KB	Output isn't correct
73	Incorrect	156 ms	16652 KB	Output isn't correct
74	Correct	253 ms	16608 KB	Output is correct
75	Correct	247 ms	16780 KB	Output is correct
76	Correct	255 ms	16496 KB	Output is correct
77	Correct	258 ms	16672 KB	Output is correct
78	Correct	276 ms	16596 KB	Output is correct
79	Correct	242 ms	16620 KB	Output is correct
80	Correct	250 ms	16600 KB	Output is correct
81	Correct	269 ms	16340 KB	Output is correct
82	Correct	246 ms	16580 KB	Output is correct
83	Correct	316 ms	16580 KB	Output is correct
84	Correct	329 ms	16600 KB	Output is correct
85	Correct	300 ms	16540 KB	Output is correct
86	Correct	309 ms	16528 KB	Output is correct
87	Correct	302 ms	16564 KB	Output is correct
88	Correct	328 ms	16704 KB	Output is correct
89	Correct	355 ms	16500 KB	Output is correct
90	Correct	346 ms	16496 KB	Output is correct
91	Correct	338 ms	16532 KB	Output is correct
92	Correct	319 ms	16656 KB	Output is correct