Submission #1096067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096067		thangdz2k7	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	817 ms	70632 KiB

joioi

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 2e3 + 5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, m, a[N][N], mn = mod, mx = 0, b[N][N];

bool check(int val){
    for (int i = 0; i < n; ++ i){
        for (int j = 0; j < m; ++ j){
            b[i][j] = 0;
            if (a[i][j] <= mn + val) b[i][j] |= 1;
            if (a[i][j] >= mx - val) b[i][j] |= 2;
            if (!b[i][j]) return false;
        }
    }

    for (int t : {1, 2}){
        int cur = m - 1; bool ck = true;
        for (int i = 0; i < n; ++ i){
            int fir = m, las = -1;
            for (int j = 0; j < m; ++ j){
                if (b[i][j] == t) las = j;
                if (b[i][j] == (t ^ 3) && fir == m) fir = j;
            }
            minl(cur, fir - 1);
            if (cur < las){
                ck = false;
                break;
            }
        }
        if (ck) return true;

        ck = true; cur = m - 1;
        for (int i = n - 1; i >= 0; -- i){
            int fir = m, las = -1;
            for (int j = 0; j < m; ++ j){
                if (b[i][j] == t) las = j;
                if (b[i][j] == (t ^ 3) && fir == m) fir = j;
            }
            minl(cur, fir - 1);
            if (cur < las){
                ck = false;
                break;
            }
        }
        if (ck) return true;
    }

    return false;
}

void solve(){
    cin >> n >> m;
    for (int i = 0; i < n; ++ i){
        for (int j = 0; j < m; ++ j){
            cin >> a[i][j];
            maxl(mx, a[i][j]); minl(mn, a[i][j]);
        }
    }
    int lo = 0, hi = mx - mn, ans = hi;
    while (lo <= hi){
        int mid = lo + hi >> 1;
        if (check(mid)) ans = mid, hi = mid - 1;
        else lo = mid + 1;
    }
    cout << ans;
}

int main(){
    if (fopen("code.inp", "r")){
        freopen("code.inp", "r", stdin);
        freopen("code.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message (stderr)

joioi.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
joioi.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
joioi.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
joioi.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
joioi.cpp: In function 'void solve()':
joioi.cpp:78:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         int mid = lo + hi >> 1;
      |                   ~~~^~~~
joioi.cpp: In function 'int main()':
joioi.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("code.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen("code.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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