#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int N = (int)2e3+10;
int n, m, a[N][N], b[N][N];
bool chk(int R){
memset(b,0,sizeof(b));
int mn = (int)1e9, mx = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
mn = min(mn, a[i][j]), mx = max(mx, a[i][j]);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
b[i][j]=(a[i][j]>mn+R?2:a[i][j]<mx-R);
bool ok = 1;
for(int _ = 0; _ < 100; _++){
for(int i = 0; i < n and ok; i++){
for(int k : {1,2}){
int first=-1, last=-1;
for(int j = 0; j < m; j++){
if(b[i][j]==k){
if(first==-1)first=j;
last=j;
}
}
if(first==last)continue;
for(int j = first; j <= last; j++){
ok&=(!b[i][j] or b[i][j]==k);
b[i][j] = k;
}
}
}
for(int j = 0; j < m and ok; j++){
for(int k : {1,2}){
int first=-1, last=-1;
for(int i = 0; i < n; i++){
if(b[i][j]==k){
if(first==-1)first=i;
last=i;
}
}
if(first==last)continue;
for(int i = first; i <= last; i++){
ok&=(!b[i][j] or b[i][j]==k);
b[i][j] = k;
}
}
}
for(int i = 0; i < n; i++){
int first1 = -1, first2=-1;
for(int j = 0; j < m; j++){
if(!b[i][j]) continue;
if(b[i][j]==1) if(first1==-1) first1=j;
if(b[i][j]==2) if(first2==-1) first2=j;
}
if(first1==-1 or first2==-1) continue;
for(int j = 0; j < min(first1,first2); j++)
b[i][j] = (first1<first2?1:2);
int last1, last2;
for(int j = 0; j < m; j++){
if(!b[i][j]) continue;
if(b[i][j]==1) last1=j;
if(b[i][j]==2) last2=j;
}
for(int j = max(last1,last2)+1; j < m; j++)
b[i][j] = (last1>last2?1:2);
}
for(int j = 0; j < m; j++){
int first1 = -1, first2=-1;
for(int i = 0; i < n; i++){
if(!b[i][j]) continue;
if(b[i][j]==1) if(first1==-1) first1=i;
if(b[i][j]==2) if(first2==-1) first2=i;
}
if(first1==-1 or first2==-1) continue;
for(int i = 0; i < min(first1,first2); i++)
b[i][j] = (first1<first2?1:2);
int last1, last2;
for(int i = 0; i < n; i++){
if(!b[i][j]) continue;
if(b[i][j]==1) last1=i;
if(b[i][j]==2) last2=i;
}
for(int i = max(last1,last2)+1; i < n; i++)
b[i][j] = (last1>last2?1:2);
}
}
return ok;
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> a[i][j];
int l = 0, r = (int)1e9;
while(l<r){
int mid = (l+r)/2;
if(chk(mid)) r=mid;
else l=mid+1;
}
cout << l << "\n";
}
Compilation message
joioi.cpp: In function 'bool chk(int)':
joioi.cpp:81:15: warning: 'last2' may be used uninitialized in this function [-Wmaybe-uninitialized]
81 | int last1, last2;
| ^~~~~
joioi.cpp:81:8: warning: 'last1' may be used uninitialized in this function [-Wmaybe-uninitialized]
81 | int last1, last2;
| ^~~~~
joioi.cpp:62:15: warning: 'last2' may be used uninitialized in this function [-Wmaybe-uninitialized]
62 | int last1, last2;
| ^~~~~
joioi.cpp:62:8: warning: 'last1' may be used uninitialized in this function [-Wmaybe-uninitialized]
62 | int last1, last2;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
16208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
16208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
16208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
