#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN = 2010;
const ll INF = 1e18;
const ll MOD = 1e9+7;
ll N,M;
ll A[MAXN][MAXN];
ll LOW, UPP;
int B[MAXN][MAXN];
pi ones[MAXN], twos[MAXN];
bool ask(){
ll L=0;
// for (int i=1;i<=N;++i){for(int j=1;j<=M;++j)cout<<B[i][j]<<' ';cout<<'\n';}
for(int i=1;i<=N;++i){
ones[i]=mp(INF,0);
twos[i]=mp(INF,0);
for(ll j=1;j<=M;++j){
if(B[i][j]==1){
ones[i].f=min(ones[i].f,j);
ones[i].s=max(ones[i].s,j);
}else if(B[i][j]==2){
twos[i].f=min(twos[i].f,j);
twos[i].s=max(twos[i].s,j);
}
}
if(ones[i].f!=INF){
L=max(L,ones[i].s);
}
if (twos[i].f!=INF&&twos[i].f<=L)return 0;
// cout<<ones[i].f<<' '<<ones[i].s<<'\n';
// cout<<twos[i].f<<' '<<twos[i].s<<'\n';
}
return 1;
}
bool works(int L){
pi a = mp(LOW,LOW+L);
pi b = mp(UPP-L,UPP);
for(int i=1;i<=N;++i)for(int j=1;j<=N;++j){
if(A[i][j]<b.f&&A[i][j]>a.s)return 0;
if(A[i][j]<b.f)B[i][j]=1;
else if(A[i][j]>a.s)B[i][j]=2;
else B[i][j]=0;
}
for(int rep=0;rep<4;++rep){
int t=ask();
if(t)return 1;
if (rep==0||rep==2){
// flip hori
for (int i=1;i<=N;++i)for (int j=1;j+j<=M;++j){
swap(B[i][j], B[i][M+1-j]);
}
}else{
for (int i=1;i+i<=M;++i)for(int j=1;j<=M;++j){
swap(B[i][j], B[N+1-i][j]);
}
}
// break;
}
return 0;
}
int main(){
cin>>N>>M;
LOW=INF;
for (int i=1;i<=N;++i)for(int j=1;j<=M;++j){
cin>>A[i][j];
UPP=max(UPP,A[i][j]);
LOW=min(LOW,A[i][j]);
}
ll lb=0;
ll ub=UPP-LOW+1;
while(ub>lb){
int mid=(lb+ub)/2;
if(works(mid))ub=mid;
else lb=mid+1;
}
cout<<lb;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
