Submission #153248

#	Time	Username	Problem	Language	Result	Execution time	Memory
153248		arnold518	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	948 ms	54880 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;

int H, W, A[MAXN+10][MAXN+10];
int minval=2e9, maxval=-1;

bool decide(int x)
{
    int i, j, t;
    int p=minval+x+1, q=maxval-x-1;
    bool flag;
    vector<pii> V;

    flag=true; V.clear();
    for(i=1; i<=H; i++)
    {
        int s=0, e=W+1;
        for(j=1; j<=W; j++) if(minval<=A[i][j] && A[i][j]<=q) s=j;
        for(j=W; j>=1; j--) if(p<=A[i][j] && A[i][j]<=maxval) e=j;
        if(e<=s) { flag=false; break; }
        V.push_back({s, e-1});
    }
    if(flag)
    {
        t=0; flag=true;
        for(i=0; i<H; i++)
        {
            if(t<V[i].first) t=V[i].first;
            else if(t>V[i].second) { flag=false; break; }
        }
        if(flag) return true;

        t=0; flag=true;
        for(i=H-1; i>=0; i--)
        {
            if(t<V[i].first) t=V[i].first;
            else if(t>V[i].second) { flag=false; break; }
        }
        if(flag) return true;
    }

    flag=true; V.clear();
    for(i=1; i<=H; i++)
    {
        int s=0, e=W+1;
        for(j=1; j<=W; j++) if(p<=A[i][j] && A[i][j]<=maxval) s=j;
        for(j=W; j>=1; j--) if(minval<=A[i][j] && A[i][j]<=q) e=j;
        if(e<=s) { flag=false; break; }
        V.push_back({s, e-1});
    }
    if(flag)
    {
        t=0; flag=true;
        for(i=0; i<H; i++)
        {
            if(t<V[i].first) t=V[i].first;
            else if(t>V[i].second) { flag=false; break; }
        }
        if(flag) return true;

        t=0; flag=true;
        for(i=H-1; i>=0; i--)
        {
            if(t<V[i].first) t=V[i].first;
            else if(t>V[i].second) { flag=false; break; }
        }
        if(flag) return true;
    }
    return false;
}

int main()
{
    int i, j;

    scanf("%d%d", &H, &W);
    for(i=1; i<=H; i++) for(j=1; j<=W; j++)
    {
        scanf("%d", &A[i][j]);
        minval=min(minval, A[i][j]);
        maxval=max(maxval, A[i][j]);
    }

    int lo=-1, hi=1e9;
    while(lo+1<hi)
    {
        int mid=lo+hi>>1;
        if(decide(mid)) hi=mid;
        else lo=mid;
    }
    printf("%d", hi);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:93:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=lo+hi>>1;
                 ~~^~~
joioi.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &H, &W);
     ~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i][j]);
         ~~~~~^~~~~~~~~~~~~~~~

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