Submission #1180002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180002		M_W_13	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	1143 ms	94660 KiB

joioi

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
const int MAXN = 3007;
int kt[MAXN][MAXN];
int T[MAXN][MAXN];
int n, m;
int kolumna[MAXN][2][2];
pair<int, int> przedzial[MAXN];

struct trojka {
    int x, y;
    int a;
};

vector<trojka> v;

bool spr(int d) {
    // cout << "d = " << d << '\n';
    rep(i, n) {
        rep(c, 2) {
            kolumna[i][c][0] = -1;
            kolumna[i][c][1] = MAXN + 1;
        }
        rep(j, m) {
            kt[i][j] = 0;
        }
    }
    int sz = v.size();
    trojka tmin = v[0];
    trojka tmax = v[sz - 1];
    // cout << tmin.a << " " << tmax.a << '\n';
    int it = 0;
    while (it < sz && (v[it].a < (tmax.a - d))) {
        // cout << "v = " << v[it].a << '\n';
        kt[v[it].x][v[it].y] = 1;
        kolumna[v[it].x][0][0] = max(kolumna[v[it].x][0][0], v[it].y);
        kolumna[v[it].x][0][1] = min(kolumna[v[it].x][0][1], v[it].y);
        it++;
    }
    it = sz - 1;
    while (it >= 0 && (v[it].a > (tmin.a + d))) {
        if (kt[v[it].x][v[it].y] == 1) {
            return false;
        }
        kt[v[it].x][v[it].y] = 2;
        kolumna[v[it].x][1][0] = max(kolumna[v[it].x][1][0], v[it].y);
        kolumna[v[it].x][1][1] = min(kolumna[v[it].x][1][1], v[it].y);
        it--;
    }
    // cout << "d = " << d << '\n';
    bool czy = false;
    bool czy1 = true;
    int wys = 0;
    int wys2 = MAXN;
    // rep(i, n) {
    //     rep(c, 2) {
    //         cout << kolumna[i][c][0] << " " << kolumna[i][c][1] << '\n';
    //     }
    //     cout << '\n';
    // }
    rep(i, n) {
        if (kolumna[i][0][0] > kolumna[i][1][1]) {
            czy1 = false;
            break;
        }
        przedzial[i] = {kolumna[i][0][0] + 1, kolumna[i][1][1]};
    }
    // if (czy1) {
    //     cout << "TAK1" << '\n';
    //     cout << "d = " << d << '\n';
    //     rep(i, n) {
    //         cout << przedzial[i].st << " " << przedzial[i].nd << '\n';
    //     }
    // }
    rep(i, n) {
        if (przedzial[i].nd < wys) {
            wys = MAXN;
        }
        else {
            wys = max(przedzial[i].st, wys);
        }
        // cout << "wys2 = " << wys2 << '\n';
        if (przedzial[i].st > wys2) {
            wys2 = -1;
        }
        else {
            wys2 = min(wys2, przedzial[i].nd);
        }
    }
    // cout << wys2 << '\n';
    if (wys == MAXN && wys2 == -1) {
        czy1 = false;
    }
    bool czy2 = true;
    wys = 0;
    wys2 = MAXN;
    rep(i, n) {
        if (kolumna[i][0][1] < kolumna[i][1][0]) {
            czy2 = false;
            break;
        }
        przedzial[i] = {kolumna[i][1][0] + 1, kolumna[i][0][1]};
    }
    // if (czy2) {
    //     cout << "TAK2" << '\n';
    //     cout << "d = " << d << '\n';
    //     rep(i, n) {
    //         cout << przedzial[i].st << " " << przedzial[i].nd << '\n';
    //     }
    // }
    rep(i, n) {
        if (przedzial[i].nd < wys) {
            wys = MAXN;
        }
        else {
            wys = max(przedzial[i].st, wys);
        }
        if (przedzial[i].st > wys2) {
            wys2 = -1;
        }
        else {
            wys2 = min(wys2, przedzial[i].nd);
        }
    }
    if (wys == MAXN && wys2 == -1) {
        czy2 = false;
    }
    if (czy1 || czy2) {
        return true;
    }
    return false;
}

bool por(trojka a, trojka b) {
    return a.a < b.a;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int mini = 1e9 + 1;
    int maks = -1;
    rep(i, n) {
        rep(j, m) {
            cin >> T[i][j];
            v.pb({i, j, T[i][j]});
            mini = min(mini, T[i][j]);
            maks = max(maks, T[i][j]);
        }
    }
    sort(v.begin(), v.end(), por);
    int ans = maks - mini;
    int poc = 0;
    int kon = ans;
    while (poc < kon) {
        int sr = (poc + kon)/2;
        if (spr(sr)) {
            ans = sr;
            kon = sr;
        }
        else {
            poc = sr + 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

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