Submission #939995

#	Time	Username	Problem	Language	Result	Execution time	Memory
939995		qwe1rt1yuiop1	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	417 ms	54960 KiB

joioi

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

int n, m, mx, mn;
vector<vector<int>> v;

int f1(int mid)
{
    vector<int> tmp(n);
    int x = 0;
    for (int i = 0; i < n; ++i)
    {
        int cur = m - 1;
        for (; cur >= 0; --cur)
            if (v[i][cur] < mx - mid)
                break;
        ++cur;
        x = max(x, cur);
        tmp[i] = x;
        for (int j = 0; j < x; ++j)
            if (v[i][j] > mn + mid)
                return 0;
        for (int j = x; j < m; ++j)
            if (v[i][j] < mx - mid)
                return 0;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < tmp[i]; ++j)
            assert(v[i][j] <= mn + mid);
        for (int j = tmp[i]; j < m; ++j)
            assert(v[i][j] >= mx - mid);
    }
    return 1;
}

int f2(int mid)
{
    vector<int> tmp(n);
    int x = 0;
    for (int i = 0; i < n; ++i)
    {
        int cur = m - 1;
        for (; cur >= 0; --cur)
            if (v[i][cur] > mn + mid)
                break;
        ++cur;
        x = max(x, cur);
        tmp[i] = x;
        for (int j = 0; j < x; ++j)
            if (v[i][j] < mx - mid)
                return 0;
        for (int j = x; j < m; ++j)
            if (v[i][j] > mn + mid)
                return 0;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < tmp[i]; ++j)
            assert(v[i][j] >= mx - mid);
        for (int j = tmp[i]; j < m; ++j)
            assert(v[i][j] <= mn + mid);
    }
    return 1;
}

int f3(int mid)
{
    vector<int> tmp(n);
    int x = m - 1;
    for (int i = 0; i < n; ++i)
    {
        int cur = 0;
        for (; cur < m; ++cur)
            if (v[i][cur] < mx - mid)
                break;
        --cur;
        x = min(x, cur);
        tmp[i] = x;
        for (int j = x + 1; j < m; ++j)
            if (v[i][j] > mn + mid)
                return 0;
        for (int j = 0; j <= x; ++j)
            if (v[i][j] < mx - mid)
                return 0;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= tmp[i]; ++j)
            assert(v[i][j] >= mx - mid);
        for (int j = tmp[i] + 1; j < m; ++j)
            assert(v[i][j] <= mn + mid);
    }
    return 1;
}

int f4(int mid)
{
    vector<int> tmp(n);
    int x = m - 1;
    for (int i = 0; i < n; ++i)
    {
        int cur = 0;
        for (; cur < m; ++cur)
            if (v[i][cur] > mn + mid)
                break;
        --cur;
        x = min(x, cur);
        tmp[i] = x;
        for (int j = x + 1; j < m; ++j)
            if (v[i][j] < mx - mid)
                return 0;
        for (int j = 0; j <= x; ++j)
            if (v[i][j] > mn + mid)
                return 0;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= tmp[i]; ++j)
            assert(v[i][j] <= mn + mid);
        for (int j = tmp[i] + 1; j < m; ++j)
            assert(v[i][j] >= mx - mid);
    }
    return 1;
}

void solve()
{
    cin >> n >> m;
    v.assign(n, vector<int>(m));
    mx = 0, mn = INT_MAX;
    for (auto &i : v)
        for (auto &j : i)
            cin >> j, mx = max(mx, j), mn = min(mn, j);

    int l = 0, r = 1000000005;
    while (l < r)
    {
        int mid = (l + r) >> 1;

        if (f1(mid) || f2(mid) || f3(mid) || f4(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << '\n';
}

/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10

8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16

 */

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

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