oj.uz

Submission #742711

# Submission time Handle Problem Language Result Execution time Memory
742711 2023-05-16T18:43:22 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;
			}
		}
	}
	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)});
					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 0 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 Runtime error 186 ms 65536 KB Execution killed with signal 9
8 Correct 1 ms 212 KB Output is correct
9 Correct 13 ms 4092 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 2 ms 340 KB Output isn't correct
14 Correct 10 ms 456 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Incorrect 4 ms 340 KB Output isn't correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 19 ms 1016 KB Output isn't correct
19 Incorrect 1 ms 340 KB Output isn't correct
20 Incorrect 104 ms 5152 KB Output isn't correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Runtime error 148 ms 65536 KB Execution killed with signal 9
23 Incorrect 1 ms 340 KB Output isn't correct
24 Runtime error 157 ms 65536 KB Execution killed with signal 9
25 Incorrect 1 ms 340 KB Output isn't correct
26 Runtime error 176 ms 65536 KB Execution killed with signal 9
27 Incorrect 1 ms 340 KB Output isn't correct
28 Runtime error 167 ms 65536 KB Execution killed with signal 9
29 Incorrect 1 ms 340 KB Output isn't correct
30 Runtime error 154 ms 65536 KB Execution killed with signal 9
31 Incorrect 1 ms 468 KB Output isn't correct
32 Runtime error 145 ms 65536 KB Execution killed with signal 9
33 Incorrect 12 ms 3412 KB Output isn't correct
34 Runtime error 149 ms 65536 KB Execution killed with signal 9
35 Runtime error 140 ms 65536 KB Execution killed with signal 9
36 Incorrect 16 ms 4324 KB Output isn't correct
37 Runtime error 145 ms 65536 KB Execution killed with signal 9
38 Runtime error 171 ms 65536 KB Execution killed with signal 9
39 Incorrect 22 ms 5376 KB Output isn't correct
40 Runtime error 175 ms 65536 KB Execution killed with signal 9
41 Runtime error 145 ms 65536 KB Execution killed with signal 9
42 Incorrect 27 ms 6512 KB Output isn't correct
43 Runtime error 144 ms 65536 KB Execution killed with signal 9
44 Runtime error 150 ms 65536 KB Execution killed with signal 9
45 Incorrect 31 ms 7868 KB Output isn't correct
46 Runtime error 165 ms 65536 KB Execution killed with signal 9
47 Runtime error 148 ms 65536 KB Execution killed with signal 9
48 Incorrect 37 ms 9272 KB Output isn't correct
49 Runtime error 150 ms 65536 KB Execution killed with signal 9
50 Runtime error 149 ms 65536 KB Execution killed with signal 9
51 Incorrect 45 ms 10804 KB Output isn't correct
52 Runtime error 160 ms 65536 KB Execution killed with signal 9
53 Runtime error 157 ms 65536 KB Execution killed with signal 9
54 Incorrect 49 ms 12480 KB Output isn't correct
55 Runtime error 167 ms 65536 KB Execution killed with signal 9
56 Runtime error 160 ms 65536 KB Execution killed with signal 9
57 Incorrect 56 ms 14308 KB Output isn't correct
58 Runtime error 151 ms 65536 KB Execution killed with signal 9
59 Runtime error 192 ms 65536 KB Execution killed with signal 9
60 Incorrect 65 ms 16204 KB Output isn't correct
61 Runtime error 156 ms 65536 KB Execution killed with signal 9
62 Runtime error 177 ms 65536 KB Execution killed with signal 9
63 Correct 434 ms 16168 KB Output is correct
64 Runtime error 254 ms 65536 KB Execution killed with signal 9
65 Correct 781 ms 16200 KB Output is correct
66 Correct 573 ms 16240 KB Output is correct
67 Correct 431 ms 16184 KB Output is correct
68 Runtime error 207 ms 65536 KB Execution killed with signal 9
69 Runtime error 202 ms 65536 KB Execution killed with signal 9
70 Runtime error 241 ms 65536 KB Execution killed with signal 9
71 Execution timed out 1087 ms 20412 KB Time limit exceeded
72 Runtime error 192 ms 65536 KB Execution killed with signal 9
73 Execution timed out 1085 ms 65536 KB Time limit exceeded
74 Runtime error 194 ms 65536 KB Execution killed with signal 9
75 Runtime error 423 ms 65536 KB Execution killed with signal 9
76 Execution timed out 1056 ms 22456 KB Time limit exceeded
77 Runtime error 196 ms 65536 KB Execution killed with signal 9
78 Runtime error 204 ms 65536 KB Execution killed with signal 9
79 Runtime error 347 ms 65536 KB Execution killed with signal 9
80 Runtime error 175 ms 65536 KB Execution killed with signal 9
81 Execution timed out 1098 ms 65532 KB Time limit exceeded
82 Runtime error 182 ms 65536 KB Execution killed with signal 9
83 Runtime error 234 ms 65536 KB Execution killed with signal 9
84 Runtime error 199 ms 65536 KB Execution killed with signal 9
85 Runtime error 185 ms 65536 KB Execution killed with signal 9
86 Runtime error 184 ms 65536 KB Execution killed with signal 9
87 Runtime error 204 ms 65536 KB Execution killed with signal 9
88 Runtime error 191 ms 65536 KB Execution killed with signal 9
89 Runtime error 172 ms 65536 KB Execution killed with signal 9
90 Runtime error 205 ms 65536 KB Execution killed with signal 9
91 Runtime error 173 ms 65536 KB Execution killed with signal 9
92 Runtime error 171 ms 65536 KB Execution killed with signal 9