oj.uz

Submission #1096067

# Submission time Handle Problem Language Result Execution time Memory
1096067 2024-10-03T16:40:43 Z thangdz2k7 The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 817 ms 70632 KB 
// 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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2520 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2520 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2524 KB Output is correct
16 Correct 3 ms 3876 KB Output is correct
17 Correct 7 ms 3932 KB Output is correct
18 Correct 4 ms 3932 KB Output is correct
19 Correct 8 ms 3932 KB Output is correct
20 Correct 6 ms 3828 KB Output is correct
21 Correct 10 ms 4292 KB Output is correct
22 Correct 5 ms 4184 KB Output is correct
23 Correct 8 ms 4188 KB Output is correct
24 Correct 4 ms 3932 KB Output is correct
25 Correct 12 ms 4188 KB Output is correct
26 Correct 8 ms 4168 KB Output is correct
27 Correct 9 ms 4292 KB Output is correct
28 Correct 8 ms 4296 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2520 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2524 KB Output is correct
16 Correct 3 ms 3876 KB Output is correct
17 Correct 7 ms 3932 KB Output is correct
18 Correct 4 ms 3932 KB Output is correct
19 Correct 8 ms 3932 KB Output is correct
20 Correct 6 ms 3828 KB Output is correct
21 Correct 10 ms 4292 KB Output is correct
22 Correct 5 ms 4184 KB Output is correct
23 Correct 8 ms 4188 KB Output is correct
24 Correct 4 ms 3932 KB Output is correct
25 Correct 12 ms 4188 KB Output is correct
26 Correct 8 ms 4168 KB Output is correct
27 Correct 9 ms 4292 KB Output is correct
28 Correct 8 ms 4296 KB Output is correct
29 Correct 436 ms 53076 KB Output is correct
30 Correct 446 ms 53260 KB Output is correct
31 Correct 654 ms 54864 KB Output is correct
32 Correct 432 ms 55120 KB Output is correct
33 Correct 227 ms 49236 KB Output is correct
34 Correct 499 ms 54876 KB Output is correct
35 Correct 747 ms 70460 KB Output is correct
36 Correct 374 ms 65336 KB Output is correct
37 Correct 817 ms 70632 KB Output is correct