Submission #742704

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742704	2023-05-16T18:38:37 Z	airths	Mecho (IOI09_mecho)	C++17	39 / 100	523 ms	16748 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;
			}
		}
	}
	// 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	1 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	352 ms	16488 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Incorrect	1 ms	340 KB	Output isn't correct
13	Incorrect	1 ms	320 KB	Output isn't correct
14	Correct	2 ms	428 KB	Output is correct
15	Incorrect	1 ms	212 KB	Output isn't correct
16	Incorrect	0 ms	212 KB	Output isn't correct
17	Incorrect	1 ms	340 KB	Output isn't correct
18	Incorrect	1 ms	340 KB	Output isn't correct
19	Incorrect	1 ms	340 KB	Output isn't correct
20	Incorrect	1 ms	340 KB	Output isn't correct
21	Incorrect	1 ms	320 KB	Output isn't correct
22	Incorrect	1 ms	316 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	468 KB	Output isn't correct
33	Incorrect	13 ms	3488 KB	Output isn't correct
34	Incorrect	14 ms	3528 KB	Output isn't correct
35	Incorrect	66 ms	3520 KB	Output isn't correct
36	Incorrect	15 ms	4452 KB	Output isn't correct
37	Incorrect	18 ms	4428 KB	Output isn't correct
38	Incorrect	83 ms	4500 KB	Output isn't correct
39	Incorrect	20 ms	5548 KB	Output isn't correct
40	Incorrect	21 ms	5584 KB	Output isn't correct
41	Incorrect	104 ms	5588 KB	Output isn't correct
42	Incorrect	24 ms	6768 KB	Output isn't correct
43	Incorrect	31 ms	6752 KB	Output isn't correct
44	Incorrect	132 ms	6748 KB	Output isn't correct
45	Incorrect	30 ms	8104 KB	Output isn't correct
46	Incorrect	35 ms	8084 KB	Output isn't correct
47	Incorrect	164 ms	8156 KB	Output isn't correct
48	Incorrect	36 ms	9540 KB	Output isn't correct
49	Incorrect	37 ms	9608 KB	Output isn't correct
50	Incorrect	202 ms	9536 KB	Output isn't correct
51	Incorrect	45 ms	11108 KB	Output isn't correct
52	Incorrect	45 ms	11040 KB	Output isn't correct
53	Incorrect	246 ms	11216 KB	Output isn't correct
54	Incorrect	50 ms	12764 KB	Output isn't correct
55	Incorrect	53 ms	12792 KB	Output isn't correct
56	Incorrect	289 ms	12736 KB	Output isn't correct
57	Incorrect	58 ms	14548 KB	Output isn't correct
58	Incorrect	60 ms	14544 KB	Output isn't correct
59	Incorrect	354 ms	14520 KB	Output isn't correct
60	Incorrect	64 ms	16504 KB	Output isn't correct
61	Incorrect	69 ms	16472 KB	Output isn't correct
62	Incorrect	396 ms	16448 KB	Output isn't correct
63	Correct	316 ms	16444 KB	Output is correct
64	Incorrect	523 ms	16476 KB	Output isn't correct
65	Correct	429 ms	16516 KB	Output is correct
66	Correct	345 ms	16424 KB	Output is correct
67	Correct	310 ms	16428 KB	Output is correct
68	Correct	171 ms	16496 KB	Output is correct
69	Correct	153 ms	16484 KB	Output is correct
70	Correct	138 ms	16476 KB	Output is correct
71	Correct	149 ms	16552 KB	Output is correct
72	Incorrect	113 ms	16640 KB	Output isn't correct
73	Incorrect	167 ms	16680 KB	Output isn't correct
74	Correct	251 ms	16648 KB	Output is correct
75	Correct	255 ms	16748 KB	Output is correct
76	Correct	245 ms	16636 KB	Output is correct
77	Correct	245 ms	16612 KB	Output is correct
78	Correct	277 ms	16596 KB	Output is correct
79	Correct	247 ms	16624 KB	Output is correct
80	Correct	233 ms	16592 KB	Output is correct
81	Correct	269 ms	16596 KB	Output is correct
82	Correct	243 ms	16612 KB	Output is correct
83	Correct	313 ms	16532 KB	Output is correct
84	Correct	313 ms	16712 KB	Output is correct
85	Correct	303 ms	16576 KB	Output is correct
86	Correct	301 ms	16636 KB	Output is correct
87	Correct	305 ms	16540 KB	Output is correct
88	Correct	329 ms	16508 KB	Output is correct
89	Correct	354 ms	16600 KB	Output is correct
90	Correct	350 ms	16504 KB	Output is correct
91	Correct	357 ms	16520 KB	Output is correct
92	Correct	317 ms	16636 KB	Output is correct