Submission #742702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742702	2023-05-16T18:36:23 Z	airths	Mecho (IOI09_mecho)	C++17	39 / 100	492 ms	17164 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;
		}
	}
	cout<<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	320 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 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	313 ms	16928 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	0 ms	212 KB	Output is correct
12	Incorrect	1 ms	340 KB	Output isn't correct
13	Incorrect	1 ms	340 KB	Output isn't correct
14	Correct	1 ms	340 KB	Output is correct
15	Incorrect	1 ms	320 KB	Output isn't correct
16	Incorrect	1 ms	320 KB	Output isn't correct
17	Incorrect	1 ms	316 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	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	320 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	468 KB	Output isn't correct
30	Incorrect	1 ms	452 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	12 ms	3504 KB	Output isn't correct
34	Incorrect	13 ms	3528 KB	Output isn't correct
35	Incorrect	60 ms	3504 KB	Output isn't correct
36	Incorrect	16 ms	4408 KB	Output isn't correct
37	Incorrect	16 ms	4432 KB	Output isn't correct
38	Incorrect	80 ms	4472 KB	Output isn't correct
39	Incorrect	21 ms	5564 KB	Output isn't correct
40	Incorrect	21 ms	5572 KB	Output isn't correct
41	Incorrect	102 ms	5576 KB	Output isn't correct
42	Incorrect	26 ms	6752 KB	Output isn't correct
43	Incorrect	28 ms	6748 KB	Output isn't correct
44	Incorrect	120 ms	6764 KB	Output isn't correct
45	Incorrect	31 ms	8128 KB	Output isn't correct
46	Incorrect	32 ms	8124 KB	Output isn't correct
47	Incorrect	154 ms	8128 KB	Output isn't correct
48	Incorrect	37 ms	9616 KB	Output isn't correct
49	Incorrect	49 ms	9664 KB	Output isn't correct
50	Incorrect	204 ms	9628 KB	Output isn't correct
51	Incorrect	44 ms	11220 KB	Output isn't correct
52	Incorrect	44 ms	11264 KB	Output isn't correct
53	Incorrect	241 ms	11364 KB	Output isn't correct
54	Incorrect	49 ms	12964 KB	Output isn't correct
55	Incorrect	52 ms	12984 KB	Output isn't correct
56	Incorrect	297 ms	12964 KB	Output isn't correct
57	Incorrect	58 ms	14848 KB	Output isn't correct
58	Incorrect	61 ms	14836 KB	Output isn't correct
59	Incorrect	355 ms	14832 KB	Output isn't correct
60	Incorrect	62 ms	16840 KB	Output isn't correct
61	Incorrect	63 ms	16828 KB	Output isn't correct
62	Incorrect	436 ms	17012 KB	Output isn't correct
63	Correct	278 ms	16900 KB	Output is correct
64	Incorrect	492 ms	16904 KB	Output isn't correct
65	Correct	386 ms	16792 KB	Output is correct
66	Correct	315 ms	16800 KB	Output is correct
67	Correct	295 ms	16784 KB	Output is correct
68	Correct	149 ms	16876 KB	Output is correct
69	Correct	138 ms	16860 KB	Output is correct
70	Correct	134 ms	16872 KB	Output is correct
71	Correct	131 ms	16844 KB	Output is correct
72	Incorrect	105 ms	16872 KB	Output isn't correct
73	Incorrect	135 ms	17044 KB	Output isn't correct
74	Correct	211 ms	17020 KB	Output is correct
75	Correct	222 ms	17000 KB	Output is correct
76	Correct	251 ms	17164 KB	Output is correct
77	Correct	226 ms	16992 KB	Output is correct
78	Correct	273 ms	16972 KB	Output is correct
79	Correct	209 ms	16980 KB	Output is correct
80	Correct	222 ms	17052 KB	Output is correct
81	Correct	262 ms	16960 KB	Output is correct
82	Correct	230 ms	16960 KB	Output is correct
83	Correct	299 ms	16904 KB	Output is correct
84	Correct	275 ms	17028 KB	Output is correct
85	Correct	285 ms	16960 KB	Output is correct
86	Correct	288 ms	16908 KB	Output is correct
87	Correct	315 ms	17020 KB	Output is correct
88	Correct	309 ms	16888 KB	Output is correct
89	Correct	316 ms	16900 KB	Output is correct
90	Correct	325 ms	16908 KB	Output is correct
91	Correct	354 ms	17000 KB	Output is correct
92	Correct	325 ms	16880 KB	Output is correct