Submission #1156231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156231		mocha	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	0 ms	328 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
const int mx = 2e3+5;
const int inf = 1e9+5;

int n, m;
int a[mx][mx];
int b[mx][mx];
int mn = inf, ma = 0;
int IOI, JOI;

bool check1(int x) {
    int pre = m;
    for (int i=1;i<=n;i++) {
        int mn = m+1;
        int ma = 0;
        for (int j=1;j<=m;j++) {
            if (abs(IOI-a[i][j]) > x) ma = max(ma, j);
            if (abs(JOI-a[i][j]) > x) mn = min(mn, j);
            if (abs(IOI-a[i][j]) > x and abs(JOI-a[i][j]) > x) return 0;
        }
        if (mn < ma or ma > pre) return 0;
        pre = min(pre, mn-1);
    }
    return true;
}

bool check2(int x) {
    int pre = m;
    for (int i=1;i<=n;i++) {
        int mn = m+1;
        int ma = 0;
        for (int j=1;j<=m;j++) {
            if (abs(IOI-b[i][j]) > x) ma = max(ma, j);
            if (abs(JOI-b[i][j]) > x) mn = min(mn, j);
        }
        if (mn < ma or ma > pre) return 0;
        pre = min(pre, mn-1);
    }
    return true;
}

signed main() {
    cin >> n >> m;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            cin >> a[i][j];
            mn = min(mn, a[i][j]);
            ma = max(ma, a[i][j]);
            b[n-i+1][j] = a[i][j];
        }
    }
    IOI = ma;
    JOI = mn;
    int l = 0, r = ma - mn;
    while (l < r) {
        int m = l + r >> 1;
        if (check1(m) or check2(m)) {
            r = m;
        } else {
            l = m+1;
        }
    }
    int ans = l;
    {
        IOI = mn;
        JOI = ma;
        int l = 0, r = ma - mn;
        while (l < r) {
            int m = l + r >> 1;
            if (check1(m) or check2(m)) {
                r = m;
            } else {
                l = m+1;
            }
        }
        ans = min(ans, l);
    }
    cout << ans << "\n";
}

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