oj.uz

Submission #882840

# Submission time Handle Problem Language Result Execution time Memory
882840 2023-12-03T20:18:44 Z abhinavshukla408 Mecho (IOI09_mecho) C++17
31 / 100
 321 ms 31124 KB 
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <math.h>
 
using namespace std;
 
#define endl "\n"
#define int int64_t 
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FOR0(i,a) FOR(i,0,a)
#define FOR1(i,a) for (int i = (1); i <= (a); ++i)
#define TRAV(a,x) for (auto& a: x)

using pii = pair<int,int>;
using vi = vector<int>;
vi dx = {-1,0,1,0};
vi dy = {0,-1,0,1};
const int NMAX=800;
int N;
int S;
pii start={0,0};
pii end2={0,0};

bool f(int k,string grid[NMAX][NMAX],int distBees[NMAX][NMAX]){
	queue<pii> cur;
	cur.push(start);
	int dist[N][N];
	FOR0(i,N){
		FOR0(j,N){
			dist[i][j]=-1;
		}
	}
	dist[start.first][start.second]=0;
	while(!cur.empty()){
		pii curNode=cur.front();
		cur.pop();
		FOR0(i,4){
			int newR=curNode.first+dx[i];
			int newC=curNode.second+dy[i];
			if(newR<0 || newR>=N || newC<0 || newC>=N){continue;}
			if((grid[newR][newC]=="G" || grid[newR][newC]=="D") && dist[newR][newC]==(-1)){
				if((distBees[newR][newC]-k)>((dist[curNode.first][curNode.second]+1)/S)){
					//cout<<newR<<" "<<newC<<endl;
					dist[newR][newC]=dist[curNode.first][curNode.second]+1;
					cur.push({newR,newC});
				}
			}
		}
	}
	bool ans=false;
	FOR0(i,4){
			int newR=end2.first+dx[i];
			int newC=end2.second+dy[i];
			if(newR<0 || newR>=N || newC<0 || newC>=N){continue;}
			if((grid[newR][newC]=="G" || grid[newR][newC]=="D") && dist[newR][newC]!=(-1)){
				
					//cout<<newR<<" "<<newC<<endl;
					ans=true;
				
			}
	}
	return ans;

}

int last_true(int lo, int hi,string grid[NMAX][NMAX],int distBees[NMAX][NMAX]) {
	// if none of the values in the range work, return lo - 1
	lo--;
	while (lo < hi) {
		// find the middle of the current range (rounding up)
		int mid = lo + (hi - lo + 1) / 2;
		if (f(mid,grid,distBees)) {
			// if mid works, then all numbers smaller than mid also work
			lo = mid;
		} else {
			// if mid does not work, greater values would not work either
			hi = mid - 1;
		}
	}
	return lo;
}


int32_t main(){

	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	// cout<<"yo"<<endl;
	// return 0;
	cin>>N>>S;
	string grid[NMAX][NMAX];
	int distBees[NMAX][NMAX];
	
	queue<pii> cur;
	FOR0(r,N){
		string in;
		cin>>in;
		FOR0(c,N){
			distBees[r][c]=-1;
			grid[r][c]=(in.at(c));
			if(grid[r][c]=="H"){
				cur.push({r,c});
				distBees[r][c]=0;
			}
			if(grid[r][c]=="M"){
				start={r,c};
			}
			if(grid[r][c]=="D"){
				end2={r,c};
			}
		}
	}
	// return 0;
	while(!cur.empty()){
		pii curNode=cur.front();
		int curR=curNode.first;
		int curC=curNode.second;
		cur.pop();
		FOR0(i,4){
				int newR=curNode.first+dx[i];
				int newC=curNode.second+dy[i];
				if(newR<0 || newR>=N || newC<0 || newC>=N){continue;}
				if(grid[newR][newC]!="M" && distBees[newR][newC]==(-1)){
					distBees[newR][newC]=distBees[curR][curC]+1;
					cur.push({newR,newC});
				}
		}
	}
	//return 0;
	int ans=last_true(0,100000000,grid,distBees);
	if(ans==100000000){
		ans=-1;
	}
	cout<<ans<<endl;
	



	return 0;
}

Subtask #1
31.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25436 KB Output is correct
2 Correct 16 ms 25432 KB Output is correct
3 Correct 18 ms 25388 KB Output is correct
4 Incorrect 15 ms 25436 KB Output isn't correct
5 Incorrect 15 ms 25412 KB Output isn't correct
6 Correct 15 ms 25436 KB Output is correct
7 Correct 188 ms 30600 KB Output is correct
8 Correct 16 ms 25436 KB Output is correct
9 Incorrect 15 ms 25484 KB Output isn't correct
10 Correct 15 ms 25500 KB Output is correct
11 Correct 14 ms 25436 KB Output is correct
12 Incorrect 15 ms 25328 KB Output isn't correct
13 Incorrect 16 ms 25432 KB Output isn't correct
14 Correct 15 ms 25688 KB Output is correct
15 Incorrect 15 ms 25436 KB Output isn't correct
16 Incorrect 16 ms 25436 KB Output isn't correct
17 Incorrect 15 ms 25436 KB Output isn't correct
18 Incorrect 14 ms 25436 KB Output isn't correct
19 Incorrect 18 ms 25436 KB Output isn't correct
20 Incorrect 16 ms 25436 KB Output isn't correct
21 Incorrect 15 ms 25436 KB Output isn't correct
22 Incorrect 17 ms 25436 KB Output isn't correct
23 Incorrect 15 ms 25328 KB Output isn't correct
24 Incorrect 15 ms 25484 KB Output isn't correct
25 Incorrect 15 ms 25432 KB Output isn't correct
26 Incorrect 15 ms 25436 KB Output isn't correct
27 Incorrect 15 ms 25432 KB Output isn't correct
28 Incorrect 15 ms 25436 KB Output isn't correct
29 Incorrect 15 ms 25540 KB Output isn't correct
30 Incorrect 15 ms 25436 KB Output isn't correct
31 Incorrect 16 ms 25436 KB Output isn't correct
32 Incorrect 16 ms 25436 KB Output isn't correct
33 Incorrect 25 ms 26200 KB Output isn't correct
34 Incorrect 30 ms 26460 KB Output isn't correct
35 Correct 55 ms 26444 KB Output is correct
36 Incorrect 35 ms 26536 KB Output isn't correct
37 Incorrect 30 ms 26536 KB Output isn't correct
38 Correct 71 ms 26756 KB Output is correct
39 Incorrect 36 ms 27092 KB Output isn't correct
40 Incorrect 35 ms 27224 KB Output isn't correct
41 Correct 108 ms 26960 KB Output is correct
42 Incorrect 38 ms 27540 KB Output isn't correct
43 Incorrect 38 ms 27220 KB Output isn't correct
44 Correct 111 ms 27480 KB Output is correct
45 Incorrect 47 ms 27812 KB Output isn't correct
46 Incorrect 46 ms 27732 KB Output isn't correct
47 Correct 144 ms 27876 KB Output is correct
48 Incorrect 45 ms 28240 KB Output isn't correct
49 Incorrect 52 ms 28332 KB Output isn't correct
50 Correct 188 ms 28332 KB Output is correct
51 Incorrect 57 ms 28580 KB Output isn't correct
52 Incorrect 68 ms 29012 KB Output isn't correct
53 Correct 224 ms 28828 KB Output is correct
54 Incorrect 58 ms 29112 KB Output isn't correct
55 Incorrect 76 ms 29268 KB Output isn't correct
56 Correct 231 ms 29364 KB Output is correct
57 Incorrect 71 ms 29780 KB Output isn't correct
58 Incorrect 92 ms 29872 KB Output isn't correct
59 Correct 261 ms 29880 KB Output is correct
60 Incorrect 71 ms 30376 KB Output isn't correct
61 Incorrect 87 ms 30284 KB Output isn't correct
62 Correct 319 ms 30536 KB Output is correct
63 Incorrect 85 ms 30388 KB Output isn't correct
64 Incorrect 321 ms 30520 KB Output isn't correct
65 Incorrect 234 ms 30288 KB Output isn't correct
66 Incorrect 92 ms 30372 KB Output isn't correct
67 Correct 118 ms 30380 KB Output is correct
68 Incorrect 89 ms 30684 KB Output isn't correct
69 Incorrect 107 ms 30644 KB Output isn't correct
70 Incorrect 78 ms 30804 KB Output isn't correct
71 Incorrect 78 ms 30648 KB Output isn't correct
72 Incorrect 82 ms 30692 KB Output isn't correct
73 Incorrect 105 ms 31060 KB Output isn't correct
74 Correct 142 ms 30936 KB Output is correct
75 Correct 154 ms 31124 KB Output is correct
76 Correct 152 ms 31060 KB Output is correct
77 Correct 157 ms 31056 KB Output is correct
78 Correct 200 ms 30860 KB Output is correct
79 Correct 140 ms 30800 KB Output is correct
80 Correct 154 ms 30872 KB Output is correct
81 Correct 186 ms 30872 KB Output is correct
82 Correct 167 ms 30808 KB Output is correct
83 Correct 168 ms 30804 KB Output is correct
84 Correct 168 ms 31056 KB Output is correct
85 Correct 157 ms 30936 KB Output is correct
86 Correct 187 ms 30808 KB Output is correct
87 Correct 197 ms 30892 KB Output is correct
88 Correct 175 ms 30640 KB Output is correct
89 Correct 204 ms 30840 KB Output is correct
90 Correct 200 ms 30632 KB Output is correct
91 Correct 194 ms 30800 KB Output is correct
92 Correct 186 ms 30804 KB Output is correct