Submission #419746

#	Time	Username	Problem	Language	Result	Execution time	Memory
419746		Runtime_error_	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	1 ms	332 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,OriginalArr[inf][inf],a[inf][inf],mn = MX,mx,vis[inf][inf];
pi MaxVals;
queue<ll> q;

bool check(ll k,bool ReverseRows){
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++)
            a[i][j] = (ReverseRows?OriginalArr[n-i+1][j]:OriginalArr[i][j]);
    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;
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
                scanf("%lld",&OriginalArr[i][j]);
            mx = max(mx,OriginalArr[i][j]);
            mn = min(mn,OriginalArr[i][j]);
        }
    }

    ll l = -1, r = mx-mn+1;
    while(r-l>1){
        if(check(mid,0) || check(mid,1))
            r = mid;
        else
            l = mid;
    }
    printf("%lld\n",r);
}

Compilation message (stderr)

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

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