답안 #919142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919142	2024-01-31T11:24:54 Z	MilosMilutinovic	산악 구조대 (JOI13_mountain)	C++14	0 / 100	9 ms	1624 KB

mountain

#include "grader.h"
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
 
int n,m,x,y,v,head;
int mat[105][105],dist[205][205];
pii que[40005];
vector<pii> c[205];
 
//int Measure(int RM, int CM){ return mat[RM][CM]; }
//void Pinpoint(int RP, int CP) { printf("%d %d\n",RP,CP); }
 
bool cmp1(pii a,pii b){ return a.fi<b.fi||(a.fi==b.fi&&a.se<b.se); }
bool cmp2(pii a,pii b){ return a.fi<b.fi||(a.fi==b.fi&&a.se>b.se); }
bool cmp3(pii a,pii b){ return a.fi>b.fi||(a.fi==b.fi&&a.se<b.se); }
bool cmp4(pii a,pii b){ return a.fi>b.fi||(a.fi==b.fi&&a.se>b.se); }
 
int getmin(int d){
	int mn=(int)1e9;
	sort(c[d].begin(),c[d].end(),cmp1);
	mn=min(mn,Measure(c[d][0].fi,c[d][0].se));
	sort(c[d].begin(),c[d].end(),cmp2);
	mn=min(mn,Measure(c[d][0].fi,c[d][0].se));
	sort(c[d].begin(),c[d].end(),cmp3);
	mn=min(mn,Measure(c[d][0].fi,c[d][0].se));
	sort(c[d].begin(),c[d].end(),cmp4);
	mn=min(mn,Measure(c[d][0].fi,c[d][0].se));
	return mn;
}
 
void Rescue(int R, int C, int MR, int MC, int X){
	n=R; m=C; x=MR; y=MC; v=X;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dist[i][j]=-1;
	dist[x][y]=0;
	que[++head]=mp(x,y);
	for(int b=1;b<=head;b++){
		int i=que[b].fi,j=que[b].se;
		for(int di=-1;di<=1;di++){
			for(int dj=-1;dj<=1;dj++){
				int ni=i+di,nj=j+dj;
				if(1<=ni&&ni<=n&&1<=nj&&nj<=m&&dist[ni][nj]==-1){
					dist[ni][nj]=dist[i][j]+1;
					que[++head]=mp(ni,nj);
				}
			}
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) c[dist[i][j]].pb(mp(i,j));
	int mx=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mx=max(mx,dist[i][j]);
	int l=0,r=mx,f=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(getmin(mid)<=v) f=mid,r=mid-1; else l=mid+1;
	}
	for(auto&p:c[f]){
		if(Measure(p.fi,p.se)==v){
			Pinpoint(p.fi,p.se);
			return;
		}
	}
}

Subtask #1

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	544 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	344 KB	Output is correct
22	Correct	1 ms	344 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	1 ms	344 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	344 KB	Output is correct
27	Correct	0 ms	412 KB	Output is correct
28	Correct	0 ms	344 KB	Output is correct
29	Correct	1 ms	344 KB	Output is correct
30	Correct	0 ms	344 KB	Output is correct
31	Correct	1 ms	344 KB	Output is correct
32	Correct	1 ms	600 KB	Output is correct
33	Correct	1 ms	344 KB	Output is correct
34	Correct	1 ms	348 KB	Output is correct
35	Correct	1 ms	344 KB	Output is correct
36	Correct	1 ms	344 KB	Output is correct
37	Correct	1 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	0 ms	348 KB	Output is correct
40	Correct	1 ms	344 KB	Output is correct
41	Correct	0 ms	344 KB	Output is correct
42	Correct	0 ms	344 KB	Output is correct
43	Correct	1 ms	348 KB	Output is correct
44	Correct	1 ms	344 KB	Output is correct
45	Correct	1 ms	344 KB	Output is correct
46	Correct	1 ms	344 KB	Output is correct
47	Correct	0 ms	344 KB	Output is correct
48	Correct	1 ms	344 KB	Output is correct
49	Correct	1 ms	344 KB	Output is correct
50	Correct	1 ms	344 KB	Output is correct
51	Correct	1 ms	348 KB	Output is correct
52	Correct	1 ms	344 KB	Output is correct
53	Correct	0 ms	344 KB	Output is correct
54	Correct	1 ms	344 KB	Output is correct
55	Correct	1 ms	348 KB	Output is correct
56	Correct	1 ms	344 KB	Output is correct
57	Correct	1 ms	344 KB	Output is correct
58	Correct	0 ms	348 KB	Output is correct
59	Correct	1 ms	756 KB	Output is correct
60	Correct	0 ms	344 KB	Output is correct
61	Correct	1 ms	344 KB	Output is correct
62	Correct	0 ms	348 KB	Output is correct
63	Correct	1 ms	344 KB	Output is correct
64	Correct	1 ms	344 KB	Output is correct
65	Correct	1 ms	344 KB	Output is correct
66	Correct	1 ms	356 KB	Output is correct
67	Correct	1 ms	344 KB	Output is correct
68	Correct	1 ms	344 KB	Output is correct
69	Correct	1 ms	344 KB	Output is correct
70	Correct	1 ms	348 KB	Output is correct
71	Correct	1 ms	344 KB	Output is correct
72	Correct	0 ms	344 KB	Output is correct
73	Correct	1 ms	344 KB	Output is correct
74	Incorrect	1 ms	348 KB	Wrong Answer [5]
75	Halted	0 ms	0 KB	-

Subtask #2

0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	1624 KB	Output is correct
2	Correct	6 ms	1368 KB	Output is correct
3	Correct	6 ms	1368 KB	Output is correct
4	Correct	6 ms	1368 KB	Output is correct
5	Correct	6 ms	1368 KB	Output is correct
6	Correct	6 ms	1372 KB	Output is correct
7	Correct	7 ms	1368 KB	Output is correct
8	Correct	6 ms	1368 KB	Output is correct
9	Correct	6 ms	1368 KB	Output is correct
10	Correct	6 ms	1368 KB	Output is correct
11	Correct	6 ms	1368 KB	Output is correct
12	Correct	6 ms	1368 KB	Output is correct
13	Correct	6 ms	1368 KB	Output is correct
14	Correct	6 ms	1368 KB	Output is correct
15	Correct	9 ms	1624 KB	Output is correct
16	Correct	6 ms	1368 KB	Output is correct
17	Correct	6 ms	1368 KB	Output is correct
18	Correct	6 ms	1368 KB	Output is correct
19	Correct	6 ms	1372 KB	Output is correct
20	Correct	6 ms	1368 KB	Output is correct
21	Correct	6 ms	1368 KB	Output is correct
22	Correct	8 ms	1372 KB	Output is correct
23	Correct	6 ms	1368 KB	Output is correct
24	Correct	6 ms	1372 KB	Output is correct
25	Correct	6 ms	1372 KB	Output is correct
26	Correct	6 ms	1368 KB	Output is correct
27	Correct	7 ms	1368 KB	Output is correct
28	Correct	6 ms	1368 KB	Output is correct
29	Correct	6 ms	1368 KB	Output is correct
30	Correct	6 ms	1368 KB	Output is correct
31	Correct	6 ms	1372 KB	Output is correct
32	Correct	6 ms	1372 KB	Output is correct
33	Correct	5 ms	1372 KB	Output is correct
34	Incorrect	8 ms	1368 KB	Wrong Answer [5]
35	Halted	0 ms	0 KB	-