oj.uz

Submission #855855

# Submission time Handle Problem Language Result Execution time Memory
855855 2023-10-02T03:41:01 Z abcvuitunggio The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
int h,w,a[2001][2001],c[2001],r[2001],bc[2001],br[2001],mn=1e9,mx;
bool check(int x){
    memset(c,-1,sizeof(c));
    memset(r,-1,sizeof(r));
    memset(bc,0,sizeof(bc));
    memset(br,0,sizeof(br));
    for (int i=0;i<h;i++)
        for (int j=0;j<w;j++){
            if (a[i][j]>mn+x&&a[i][j]<mx-x)
                return false;
            if (a[i][j]>=mx-x&&a[i][j]<=mn+x)
                continue;
            int val=(a[i][j]>=mx-x);
            if (r[i]!=-1&&r[i]!=val){
                if (br[i])
                    return false;
                br[i]=1;
            }
            if (c[j]!=-1&&c[j]!=val){
                if (bc[j])
                    return false;
                bc[j]=1;
            }
            r[i]=c[j]=val;
        }
    int ch=-1;
    for (int i=0;i<h;i++)
        if (br[i]){
            if (ch!=-1&&ch!=r[i])
                return false;
            ch=r[i];
        }
    ch=-1;
    for (int i=0;i<w;i++)
        if (bc[i]){
            if (ch!=-1&&ch!=c[i])
                return false;
            ch=c[i];
        }
    return true;
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> h >> w;
    for (int i=0;i<h;i++)
        for (int j=0;j<w;j++){
            cin >> a[i][j];
            mn=min(mn,a[i][j]);
            mx=max(mx,a[i][j]);
        }
    int l=0,r=1e9,kq=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        if (check(mid)){
            kq=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout << kq;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -