/*
* Task: JOI17_JOIOI
* Lang: C/C++11
* Author: comtalyst
* Site: oj.uz
* Last Update: 16/1/2018
*/
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
using namespace std;
/* Note
----------------------------
Learned :
Bugs found & solved :
Optimizations :
----------------------------
*/
#define x first
#define y second
#define umap unordered_map
#define pqueue priority_queue
#define mset multiset
#define mp make_pair
#define mt make_tuple
#define long long long
#define MOD 1000000007
#define MAX (int)2e9
#define MIN (int)-2e9
#define FILEIN_ freopen("__in.txt","r",stdin)
#define FILEOUT_ freopen("__out.txt","w",stdout)
#define FILEIN(text) freopen(text,"r",stdin)
#define FILEOUT(text) freopen(text,"w",stdout)
bool chk[2][2005][2005];
int n,m,field[2005][2005];
pair<int,int> dr[]={{1,0},{0,1},{-1,0},{0,-1}};
bool valid(bool t,int x,int y){
if(x < 1 || y < 1 || x > n || y > m){
return false;
}
if(!chk[t][x][y]){
chk[t][x][y] = true;
return true;
}
return false;
}
main(){
int t,i,j,x,y,l,r,mid,res=MAX,nx,ny;
bool ok;
queue<pair<int,int>> q;
pair<int,pair<int,int>> mn={MAX,{MAX,MAX}},mx={MIN,{MIN,MIN}};
scanf("%d %d",&n,&m);
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
scanf("%d",&field[i][j]);
mn = min(mn,{field[i][j],{i,j}});
mx = max(mx,{field[i][j],{i,j}});
}
}
l = 0;
r = mx.x-mn.x;
while(l <= r){
mid = (l+r)/2;
memset(chk,0,sizeof chk);
chk[0][mn.y.x][mn.y.y] = true;
q.emplace(mn.y.x,mn.y.y);
while(!q.empty()){
x = q.front().x;
y = q.front().y;
q.pop();
for(i = 0; i < 4; i++){
nx = x + dr[i].x;
ny = y + dr[i].y;
if(field[nx][ny] - mn.x <= mid && valid(0,nx,ny)){
q.emplace(nx,ny);
}
}
}
chk[1][mx.y.x][mx.y.y] = true;
q.emplace(mx.y.x,mx.y.y);
while(!q.empty()){
x = q.front().x;
y = q.front().y;
q.pop();
for(i = 0; i < 4; i++){
nx = x + dr[i].x;
ny = y + dr[i].y;
if(mx.x - field[nx][ny] <= mid && valid(1,nx,ny)){
q.emplace(nx,ny);
}
}
}
/* printf(">> %d\n",mid);
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
printf("%d ",(int)chk[0][i][j] + (int)chk[1][i][j]);
}
printf("\n");
}*/
ok = true;
for(i = 1; i <= n && ok; i++){
for(j = 1; j <= m; j++){
if(!chk[0][i][j] && !chk[1][i][j]){
ok = false;
break;
}
}
}
if(ok){
res = min(res,mid);
r = mid-1;
}
else{
l = mid+1;
}
}
printf("%d\n",res);
return 0;
}
Compilation message
joioi.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
joioi.cpp: In function 'int main()':
joioi.cpp:53:6: warning: unused variable 't' [-Wunused-variable]
int t,i,j,x,y,l,r,mid,res=MAX,nx,ny;
^
joioi.cpp:58:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
^
joioi.cpp:61:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&field[i][j]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
25572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
25572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
25572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
