oj.uz

Submission #742706

# Submission time Handle Problem Language Result Execution time Memory
742706 2023-05-16T18:40:17 Z airths Mecho (IOI09_mecho) C++17
20 / 100
 1000 ms 65536 KB 
/*
 * 
 * 	^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)});
					if (j[2]==0)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
20.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 316 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Runtime error 184 ms 65536 KB Execution killed with signal 9
8 Correct 3 ms 212 KB Output is correct
9 Correct 14 ms 4072 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 324 KB Output isn't correct
13 Incorrect 3 ms 340 KB Output isn't correct
14 Correct 8 ms 468 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Incorrect 3 ms 340 KB Output isn't correct
17 Incorrect 1 ms 340 KB Output isn't correct
18 Incorrect 14 ms 1024 KB Output isn't correct
19 Incorrect 1 ms 340 KB Output isn't correct
20 Incorrect 106 ms 5228 KB Output isn't correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Runtime error 134 ms 65536 KB Execution killed with signal 9
23 Incorrect 1 ms 340 KB Output isn't correct
24 Runtime error 176 ms 65536 KB Execution killed with signal 9
25 Incorrect 1 ms 340 KB Output isn't correct
26 Runtime error 158 ms 65536 KB Execution killed with signal 9
27 Incorrect 1 ms 340 KB Output isn't correct
28 Runtime error 175 ms 65536 KB Execution killed with signal 9
29 Incorrect 1 ms 456 KB Output isn't correct
30 Runtime error 137 ms 65536 KB Execution killed with signal 9
31 Incorrect 2 ms 388 KB Output isn't correct
32 Runtime error 216 ms 65536 KB Execution killed with signal 9
33 Incorrect 16 ms 3484 KB Output isn't correct
34 Runtime error 155 ms 65536 KB Execution killed with signal 9
35 Runtime error 140 ms 65536 KB Execution killed with signal 9
36 Incorrect 17 ms 4444 KB Output isn't correct
37 Runtime error 142 ms 65536 KB Execution killed with signal 9
38 Runtime error 142 ms 65536 KB Execution killed with signal 9
39 Incorrect 20 ms 5468 KB Output isn't correct
40 Runtime error 148 ms 65536 KB Execution killed with signal 9
41 Runtime error 142 ms 65536 KB Execution killed with signal 9
42 Incorrect 26 ms 6636 KB Output isn't correct
43 Runtime error 143 ms 65536 KB Execution killed with signal 9
44 Runtime error 150 ms 65536 KB Execution killed with signal 9
45 Incorrect 34 ms 8080 KB Output isn't correct
46 Runtime error 154 ms 65536 KB Execution killed with signal 9
47 Runtime error 147 ms 65536 KB Execution killed with signal 9
48 Incorrect 39 ms 9484 KB Output isn't correct
49 Runtime error 173 ms 65536 KB Execution killed with signal 9
50 Runtime error 154 ms 65536 KB Execution killed with signal 9
51 Incorrect 41 ms 11084 KB Output isn't correct
52 Runtime error 163 ms 65536 KB Execution killed with signal 9
53 Runtime error 155 ms 65536 KB Execution killed with signal 9
54 Incorrect 50 ms 12784 KB Output isn't correct
55 Runtime error 149 ms 65536 KB Execution killed with signal 9
56 Runtime error 158 ms 65536 KB Execution killed with signal 9
57 Incorrect 57 ms 14556 KB Output isn't correct
58 Runtime error 157 ms 65536 KB Execution killed with signal 9
59 Runtime error 192 ms 65536 KB Execution killed with signal 9
60 Incorrect 67 ms 16452 KB Output isn't correct
61 Runtime error 163 ms 65536 KB Execution killed with signal 9
62 Runtime error 172 ms 65536 KB Execution killed with signal 9
63 Correct 425 ms 16428 KB Output is correct
64 Runtime error 194 ms 65536 KB Execution killed with signal 9
65 Correct 741 ms 16464 KB Output is correct
66 Correct 531 ms 16536 KB Output is correct
67 Correct 434 ms 16432 KB Output is correct
68 Runtime error 221 ms 65536 KB Execution killed with signal 9
69 Runtime error 220 ms 65536 KB Execution killed with signal 9
70 Runtime error 237 ms 65536 KB Execution killed with signal 9
71 Execution timed out 1078 ms 20928 KB Time limit exceeded
72 Runtime error 199 ms 65536 KB Execution killed with signal 9
73 Execution timed out 1076 ms 65536 KB Time limit exceeded
74 Runtime error 193 ms 65536 KB Execution killed with signal 9
75 Runtime error 413 ms 65536 KB Execution killed with signal 9
76 Execution timed out 1070 ms 22896 KB Time limit exceeded
77 Runtime error 197 ms 65536 KB Execution killed with signal 9
78 Runtime error 171 ms 65536 KB Execution killed with signal 9
79 Runtime error 365 ms 65536 KB Execution killed with signal 9
80 Runtime error 176 ms 65536 KB Execution killed with signal 9
81 Execution timed out 1090 ms 65536 KB Time limit exceeded
82 Runtime error 198 ms 65536 KB Execution killed with signal 9
83 Runtime error 240 ms 65536 KB Execution killed with signal 9
84 Runtime error 180 ms 65536 KB Execution killed with signal 9
85 Runtime error 203 ms 65536 KB Execution killed with signal 9
86 Runtime error 186 ms 65536 KB Execution killed with signal 9
87 Runtime error 189 ms 65536 KB Execution killed with signal 9
88 Runtime error 170 ms 65536 KB Execution killed with signal 9
89 Runtime error 182 ms 65536 KB Execution killed with signal 9
90 Runtime error 175 ms 65536 KB Execution killed with signal 9
91 Runtime error 176 ms 65536 KB Execution killed with signal 9
92 Runtime error 180 ms 65536 KB Execution killed with signal 9