Submission #419723

#	Time	Username	Problem	Language	Result	Execution time	Memory
419723		Runtime_error_	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	22 ms	31948 KiB

joioi

#include <bits/stdc++.h>
#define ll long long
#define pi pair<ll,ll>
#define mid (l+r)/2
#define pb push
using namespace std;
const ll inf = 2e3+9,MX = 1e9+9;
ll n,m,ts,a[inf][inf],mn = MX,mx,vis[inf][inf];
pi MaxVals;
queue<ll> q;

bool check1(ll k){
    ts++;
    ll l = n,r;
    for(ll j=1;j<=m;j++){
        ll LastReq = 0;
        for(ll i=1;i<=n;i++)
            if(a[i][j] > mn+k)
                LastReq = i;
        for(ll i=1;i<=LastReq;i++){
            if(a[i][j] < mx-k)
                return 0;
            vis[i][j] = ts;
        }
        if(LastReq)
            l = min(l,j),r = j;
    }
    for(ll j=l;j<=r;j++){
        if(a[1][j] < mx-k)
            return 0;
        vis[1][j] = ts;
    }
    ts++;
    l = n;
    for(ll j=1;j<=m;j++){
        ll LastReq = n+1;
        for(ll i=n;i>=1;i--)
            if(a[i][j]  < mx-k)
                LastReq = i;
        for(ll i=n;i>=LastReq;i--){
            if(a[i][j] > mn+k || vis[i][j] == ts-1)
                return 0;
            vis[i][j] = ts;
        }
        if(LastReq < n+1)
            l = min(l,j),r = j;
    }
    for(ll j=l;j<=r;j++){
        if(a[n][j] > mn+k || vis[n][j] == ts-1)
            return 0;
        vis[n][j] = ts;
    }
    return 1;
}

bool check2(ll k){
    ts++;
    ll l = n,r;
    for(ll j=1;j<=m;j++){
        ll LastReq = n+1;
        for(ll i=n;i>=1;i--)
            if(a[i][j] > mn+k)
                LastReq = i;
        for(ll i=n;i>=LastReq;i--){
            if(a[i][j] < mx-k)
                return 0;
            vis[i][j] = ts;
        }
        if(LastReq < n+1)
            l = min(l,j),r = j;
    }
    for(ll j=l;j<=r;j++){
        if(a[n][j] < mx-k)
            return 0;
        vis[n][j] = ts;
    }
    ts++;
    l = n;
    for(ll j=1;j<=m;j++){
        ll LastReq = 0;
        for(ll i=1;i<=n;i++)
            if(a[i][j]  < mx-k)
                LastReq = i;
        for(ll i=1;i<=LastReq;i++){
            if(a[i][j] > mn+k || vis[i][j] == ts-1)
                return 0;
            vis[i][j] = ts;
        }
        if(LastReq)
            l = min(l,j),r = j;
    }
    for(ll j=l;j<=r;j++){
        if(a[1][j] > mn+k || vis[1][j] == ts-1)
            return 0;
        vis[1][j] = ts;
    }
    return 1;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
                scanf("%lld",&a[i][j]);
            if(a[i][j] > mx)
                MaxVals = (pi(i,j)),mx = a[i][j];
            mn = min(mn,a[i][j]);
        }
    }

    ll l = -1, r = MX+2;
    while(r-l>1){
        if(check1(mid) || check2(mid))
            r = mid;
        else
            l = mid;
    }
    printf("%lld\n",r);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
joioi.cpp:103:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |                 scanf("%lld",&a[i][j]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~
joioi.cpp: In function 'bool check1(long long int)':
joioi.cpp:28:17: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |     for(ll j=l;j<=r;j++){
      |                ~^~~
joioi.cpp: In function 'bool check2(long long int)':
joioi.cpp:72:17: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |     for(ll j=l;j<=r;j++){
      |                ~^~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40