Submission #855858

#	Time	Username	Problem	Language	Result	Execution time	Memory
855858		abcvuitunggio	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	348 KiB

joioi

#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;
            int val=2;
            if (a[i][j]<mx-x||a[i][j]>mn+x)
                val=(a[i][j]>=mx-x);
            if (br[i]){
                if (val!=2&&val!=r[i])
                    return false;
                val=r[i];
            }
            if (bc[j]){
                if (val!=2&&val!=c[j])
                    return false;
                val=c[j];
            }
            if (val==2)
                continue;
            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
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40