oj.uz

Submission #882827

# Submission time Handle Problem Language Result Execution time Memory
882827 2023-12-03T19:52:43 Z abhinavshukla408 Mecho (IOI09_mecho) C++17
8 / 100
 343 ms 31076 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});
				}
			}
		}
	}

	if(dist[end2.first][end2.second]!=(-1)){
		return true;
	}
	return false;

}

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];
	int distMan[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;

	cout<<last_true(2,1000000,grid,distBees)<<endl;
	



	return 0;
}

Compilation message

mecho.cpp: In function 'int32_t main()':
mecho.cpp:95:6: warning: unused variable 'distMan' [-Wunused-variable]
   95 |  int distMan[NMAX][NMAX];
      |      ^~~~~~~

Subtask #1
8.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 25432 KB Output is correct
2 Correct 17 ms 25436 KB Output is correct
3 Correct 15 ms 25432 KB Output is correct
4 Incorrect 18 ms 25432 KB Output isn't correct
5 Incorrect 16 ms 25432 KB Output isn't correct
6 Correct 16 ms 25432 KB Output is correct
7 Incorrect 211 ms 30736 KB Output isn't correct
8 Incorrect 16 ms 25436 KB Output isn't correct
9 Incorrect 15 ms 25432 KB Output isn't correct
10 Correct 15 ms 25436 KB Output is correct
11 Correct 15 ms 25500 KB Output is correct
12 Incorrect 17 ms 25436 KB Output isn't correct
13 Incorrect 16 ms 25432 KB Output isn't correct
14 Incorrect 16 ms 25436 KB Output isn't correct
15 Incorrect 16 ms 25436 KB Output isn't correct
16 Incorrect 16 ms 25308 KB Output isn't correct
17 Incorrect 18 ms 25436 KB Output isn't correct
18 Incorrect 16 ms 25504 KB Output isn't correct
19 Incorrect 16 ms 25436 KB Output isn't correct
20 Incorrect 17 ms 25500 KB Output isn't correct
21 Incorrect 16 ms 25436 KB Output isn't correct
22 Incorrect 15 ms 25432 KB Output isn't correct
23 Incorrect 17 ms 25516 KB Output isn't correct
24 Incorrect 17 ms 25436 KB Output isn't correct
25 Incorrect 16 ms 25436 KB Output isn't correct
26 Incorrect 16 ms 25436 KB Output isn't correct
27 Incorrect 16 ms 25532 KB Output isn't correct
28 Incorrect 17 ms 25436 KB Output isn't correct
29 Incorrect 16 ms 25460 KB Output isn't correct
30 Incorrect 16 ms 25436 KB Output isn't correct
31 Incorrect 16 ms 25528 KB Output isn't correct
32 Incorrect 16 ms 25436 KB Output isn't correct
33 Incorrect 25 ms 26460 KB Output isn't correct
34 Incorrect 26 ms 26196 KB Output isn't correct
35 Correct 58 ms 26460 KB Output is correct
36 Incorrect 29 ms 26704 KB Output isn't correct
37 Incorrect 31 ms 26716 KB Output isn't correct
38 Correct 72 ms 26748 KB Output is correct
39 Incorrect 31 ms 27076 KB Output isn't correct
40 Incorrect 42 ms 26964 KB Output isn't correct
41 Correct 93 ms 27088 KB Output is correct
42 Incorrect 36 ms 27220 KB Output isn't correct
43 Incorrect 35 ms 27308 KB Output isn't correct
44 Correct 136 ms 27472 KB Output is correct
45 Incorrect 40 ms 27740 KB Output isn't correct
46 Incorrect 45 ms 27732 KB Output isn't correct
47 Correct 155 ms 27828 KB Output is correct
48 Incorrect 55 ms 28324 KB Output isn't correct
49 Incorrect 58 ms 28328 KB Output isn't correct
50 Correct 185 ms 28336 KB Output is correct
51 Incorrect 53 ms 28756 KB Output isn't correct
52 Incorrect 64 ms 28580 KB Output isn't correct
53 Correct 245 ms 28848 KB Output is correct
54 Incorrect 61 ms 29268 KB Output isn't correct
55 Incorrect 75 ms 29344 KB Output isn't correct
56 Correct 275 ms 29260 KB Output is correct
57 Incorrect 83 ms 29780 KB Output isn't correct
58 Incorrect 79 ms 29780 KB Output isn't correct
59 Correct 313 ms 29932 KB Output is correct
60 Incorrect 68 ms 30524 KB Output isn't correct
61 Incorrect 91 ms 30372 KB Output isn't correct
62 Correct 343 ms 30544 KB Output is correct
63 Incorrect 85 ms 30292 KB Output isn't correct
64 Incorrect 275 ms 30380 KB Output isn't correct
65 Incorrect 231 ms 30532 KB Output isn't correct
66 Incorrect 84 ms 30396 KB Output isn't correct
67 Incorrect 135 ms 30524 KB Output isn't correct
68 Incorrect 86 ms 30620 KB Output isn't correct
69 Incorrect 83 ms 30804 KB Output isn't correct
70 Incorrect 87 ms 30676 KB Output isn't correct
71 Incorrect 84 ms 30688 KB Output isn't correct
72 Incorrect 80 ms 30948 KB Output isn't correct
73 Incorrect 90 ms 30872 KB Output isn't correct
74 Correct 135 ms 30952 KB Output is correct
75 Correct 155 ms 30924 KB Output is correct
76 Correct 129 ms 31076 KB Output is correct
77 Correct 166 ms 30936 KB Output is correct
78 Incorrect 165 ms 31024 KB Output isn't correct
79 Correct 136 ms 30880 KB Output is correct
80 Correct 141 ms 30804 KB Output is correct
81 Correct 163 ms 31016 KB Output is correct
82 Correct 158 ms 31012 KB Output is correct
83 Incorrect 172 ms 30800 KB Output isn't correct
84 Correct 168 ms 30800 KB Output is correct
85 Correct 180 ms 30800 KB Output is correct
86 Correct 175 ms 30804 KB Output is correct
87 Correct 166 ms 30940 KB Output is correct
88 Incorrect 205 ms 30840 KB Output isn't correct
89 Correct 186 ms 30844 KB Output is correct
90 Correct 182 ms 30800 KB Output is correct
91 Correct 180 ms 30800 KB Output is correct
92 Correct 185 ms 30836 KB Output is correct