Submission #1046824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046824		underwaterkillerwhale	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2397 ms	64308 KiB

joioi

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e3 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll BASE = 137;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int n, m;
int mn;
int a[N][N];
bool dd[N][N], dd2[N][N];
bool prec[N][N], sufc[N][N];

bool check (int X) {
    rep (i, 1, n)
    rep (j, 1, m) dd[i][j] = 0;
    static queue<pair<int,int>> Q;
    rep (i, 1, n)
    rep (j, 1, m) if (a[i][j] == mn) Q.push({i, j});
    while (!Q.empty()) {
        pair<int,int> u = Q.front();
        Q.pop();
        rep (k, 0, 3) {
            int ni = u.fs + dx[k], nj = u.se + dy[k];
            if (ni >= 1 && ni <= n && nj >= 1 && nj <= m && dd[ni][nj] == 0 && a[ni][nj] <= mn + X) {
                dd[ni][nj] = 1;
                Q.push({ni, nj});
            }
        }
    }
    {
        rep (i, 1, n)
        rep (j, 1, m) dd2[i][j] = 0;
        int mnR = n;
        rep (j, 1, m) {
            rep (i, 1, mnR) {
                if (dd[i][j] == 0) {
                    mnR = i - 1;
                    break;
                }
                else dd2[i][j] = 1;
            }
        }
//        rep (i, 1, n)
//        rep (j, 1, m) cout << dd2[i][j] <<" \n"[j == m];
        int mn1 = INF, mn2 = INF, mx1 = 0, mx2 = 0;
        rep (i, 1, n) rep (j, 1, m) if (dd2[i][j]) {
            mn1 = min(mn1, a[i][j]);
            mx1 = max(mx1, a[i][j]);
        }
        else {
            mx2 = max(mx2, a[i][j]);
            mn2 = min(mn2, a[i][j]);
        }
//        cout << max(mx2 - mn2, mx1 - mn1) <<"\n";
        if (max(mx2 - mn2, mx1 - mn1) <= X) {
                return 1;
        }
    }
    {
        rep (i, 1, n)
        rep (j, 1, m) dd2[i][j] = 0;
        int mnR = 1;
        reb (j, m, 1) {
            reb (i, n, mnR) {
                if (dd[i][j] == 0) {
                    mnR = i + 1;
                    break;
                }
                else dd2[i][j] = 1;
            }
        }
        int mn1 = INF, mn2 = INF, mx1 = 0, mx2 = 0;
        rep (i, 1, n) rep (j, 1, m) if (dd2[i][j]) {
            mn1 = min(mn1, a[i][j]);
            mx1 = max(mx1, a[i][j]);
        }
        else {
            mx2 = max(mx2, a[i][j]);
            mn2 = min(mn2, a[i][j]);
        }
//        cout << mx2 <<" "<<mn2 <<"\n";
        if (max(mx2 - mn2, mx1 - mn1) <= X) return 1;
    }
    {
        rep (i, 1, n)
        rep (j, 1, m) dd2[i][j] = 0;
        int mnR = n;
        reb (j, m, 1) {
            rep (i, 1, mnR) {
                if (dd[i][j] == 0) {
                    mnR = i - 1;
                    break;
                }
                else dd2[i][j] = 1;
            }
        }
        int mn1 = INF, mn2 = INF, mx1 = 0, mx2 = 0;
        rep (i, 1, n) rep (j, 1, m) if (dd2[i][j]) {
            mn1 = min(mn1, a[i][j]);
            mx1 = max(mx1, a[i][j]);
        }
        else {
            mx2 = max(mx2, a[i][j]);
            mn2 = min(mn2, a[i][j]);
        }
//        cout << mx2 <<" "<<mn2 <<"\n";
        if (max(mx2 - mn2, mx1 - mn1) <= X) return 1;
    }
    {
        rep (i, 1, n)
        rep (j, 1, m) dd2[i][j] = 0;
        int mnR = 1;
        rep (j, 1, m) {
            reb(i, n, mnR) {
                if (dd[i][j] == 0) {
                    mnR = i + 1;
                    break;
                }
                else dd2[i][j] = 1;
            }
        }
        int mn1 = INF, mn2 = INF, mx1 = 0, mx2 = 0;
        rep (i, 1, n) rep (j, 1, m) if (dd2[i][j]) {
            mn1 = min(mn1, a[i][j]);
            mx1 = max(mx1, a[i][j]);
        }
        else {
            mx2 = max(mx2, a[i][j]);
            mn2 = min(mn2, a[i][j]);
        }
//        cout << mx2 <<" "<<mn2 <<"\n";
        if (max(mx2 - mn2, mx1 - mn1) <= X) return 1;
    }
    return 0;

}

void solution () {
    cin >> n >> m;
    rep (i, 1, n)
    rep (j, 1, m)
        cin >> a[i][j];
    mn = INF;
    rep (i, 1, n)
    rep (j, 1, m) {
        if (a[i][j] < mn) mn = a[i][j];
    }
//    cout << check(18) <<"\n";
//    return;
    int lf = 0, rt = 1e9;
    while (lf < rt) {
         int mid = lf + rt >> 1;
         if (check(mid)) rt = mid;
         else lf = mid + 1;
    }
    cout << lf <<"\n";
}


#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +2
4
1 2 3 4
2
0 3
2 1
*/

Compilation message (stderr)

joioi.cpp: In function 'void solution()':
joioi.cpp:171:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  171 |          int mid = lf + rt >> 1;
      |                    ~~~^~~~

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