Submission #919148

#TimeUsernameProblemLanguageResultExecution timeMemory
919148MilosMilutinovic산악 구조대 (JOI13_mountain)C++14
0 / 100
5 ms1624 KiB
#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(),cmp3); 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++){ if(abs(di)+abs(dj)!=1) continue; 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; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...