Submission #882839

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
882839	2023-12-03T20:18:21 Z	abhinavshukla408	Mecho (IOI09_mecho)	C++17	12 / 100	3 ms	1368 KB

mecho

#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=80;
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

12.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	604 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Incorrect	0 ms	604 KB	Output isn't correct
5	Incorrect	0 ms	604 KB	Output isn't correct
6	Correct	0 ms	604 KB	Output is correct
7	Runtime error	2 ms	860 KB	Execution killed with signal 11
8	Correct	0 ms	600 KB	Output is correct
9	Incorrect	0 ms	604 KB	Output isn't correct
10	Correct	1 ms	600 KB	Output is correct
11	Correct	0 ms	600 KB	Output is correct
12	Incorrect	1 ms	604 KB	Output isn't correct
13	Incorrect	1 ms	604 KB	Output isn't correct
14	Correct	1 ms	604 KB	Output is correct
15	Incorrect	0 ms	604 KB	Output isn't correct
16	Incorrect	1 ms	600 KB	Output isn't correct
17	Incorrect	0 ms	604 KB	Output isn't correct
18	Incorrect	1 ms	604 KB	Output isn't correct
19	Incorrect	0 ms	604 KB	Output isn't correct
20	Incorrect	0 ms	604 KB	Output isn't correct
21	Incorrect	1 ms	604 KB	Output isn't correct
22	Incorrect	1 ms	604 KB	Output isn't correct
23	Incorrect	1 ms	604 KB	Output isn't correct
24	Incorrect	1 ms	604 KB	Output isn't correct
25	Incorrect	1 ms	604 KB	Output isn't correct
26	Incorrect	1 ms	604 KB	Output isn't correct
27	Incorrect	1 ms	604 KB	Output isn't correct
28	Incorrect	1 ms	604 KB	Output isn't correct
29	Incorrect	1 ms	604 KB	Output isn't correct
30	Incorrect	1 ms	604 KB	Output isn't correct
31	Incorrect	1 ms	604 KB	Output isn't correct
32	Incorrect	1 ms	604 KB	Output isn't correct
33	Runtime error	2 ms	860 KB	Execution killed with signal 11
34	Runtime error	2 ms	860 KB	Execution killed with signal 11
35	Runtime error	2 ms	860 KB	Execution killed with signal 11
36	Runtime error	2 ms	860 KB	Execution killed with signal 11
37	Runtime error	2 ms	860 KB	Execution killed with signal 11
38	Runtime error	2 ms	860 KB	Execution killed with signal 11
39	Runtime error	2 ms	860 KB	Execution killed with signal 11
40	Runtime error	2 ms	860 KB	Execution killed with signal 11
41	Runtime error	2 ms	860 KB	Execution killed with signal 11
42	Runtime error	2 ms	860 KB	Execution killed with signal 11
43	Runtime error	2 ms	860 KB	Execution killed with signal 11
44	Runtime error	2 ms	916 KB	Execution killed with signal 11
45	Runtime error	2 ms	860 KB	Execution killed with signal 11
46	Runtime error	2 ms	860 KB	Execution killed with signal 11
47	Runtime error	2 ms	860 KB	Execution killed with signal 11
48	Runtime error	2 ms	860 KB	Execution killed with signal 11
49	Runtime error	2 ms	860 KB	Execution killed with signal 11
50	Runtime error	2 ms	860 KB	Execution killed with signal 11
51	Runtime error	2 ms	964 KB	Execution killed with signal 11
52	Runtime error	2 ms	860 KB	Execution killed with signal 11
53	Runtime error	2 ms	860 KB	Execution killed with signal 11
54	Runtime error	2 ms	856 KB	Execution killed with signal 11
55	Runtime error	2 ms	860 KB	Execution killed with signal 11
56	Runtime error	2 ms	976 KB	Execution killed with signal 11
57	Runtime error	2 ms	1112 KB	Execution killed with signal 11
58	Runtime error	2 ms	1116 KB	Execution killed with signal 11
59	Runtime error	2 ms	1112 KB	Execution killed with signal 11
60	Runtime error	3 ms	860 KB	Execution killed with signal 11
61	Runtime error	3 ms	860 KB	Execution killed with signal 11
62	Runtime error	2 ms	860 KB	Execution killed with signal 11
63	Runtime error	2 ms	1116 KB	Execution killed with signal 11
64	Runtime error	2 ms	1116 KB	Execution killed with signal 11
65	Runtime error	2 ms	1116 KB	Execution killed with signal 11
66	Runtime error	2 ms	1368 KB	Execution killed with signal 11
67	Runtime error	2 ms	1116 KB	Execution killed with signal 11
68	Runtime error	2 ms	860 KB	Execution killed with signal 11
69	Runtime error	2 ms	860 KB	Execution killed with signal 11
70	Runtime error	2 ms	860 KB	Execution killed with signal 11
71	Runtime error	2 ms	860 KB	Execution killed with signal 11
72	Runtime error	2 ms	860 KB	Execution killed with signal 11
73	Runtime error	2 ms	1116 KB	Execution killed with signal 11
74	Runtime error	2 ms	860 KB	Execution killed with signal 11
75	Runtime error	2 ms	1116 KB	Execution killed with signal 11
76	Runtime error	2 ms	860 KB	Execution killed with signal 11
77	Runtime error	2 ms	860 KB	Execution killed with signal 11
78	Runtime error	3 ms	1116 KB	Execution killed with signal 11
79	Runtime error	2 ms	1116 KB	Execution killed with signal 11
80	Runtime error	2 ms	1116 KB	Execution killed with signal 11
81	Runtime error	2 ms	1116 KB	Execution killed with signal 11
82	Runtime error	2 ms	1116 KB	Execution killed with signal 11
83	Runtime error	2 ms	860 KB	Execution killed with signal 11
84	Runtime error	2 ms	860 KB	Execution killed with signal 11
85	Runtime error	2 ms	860 KB	Execution killed with signal 11
86	Runtime error	2 ms	860 KB	Execution killed with signal 11
87	Runtime error	3 ms	860 KB	Execution killed with signal 11
88	Runtime error	2 ms	1112 KB	Execution killed with signal 11
89	Runtime error	3 ms	860 KB	Execution killed with signal 11
90	Runtime error	2 ms	856 KB	Execution killed with signal 11
91	Runtime error	2 ms	860 KB	Execution killed with signal 11
92	Runtime error	2 ms	860 KB	Execution killed with signal 11