oj.uz

Submission #1081155

# Submission time Handle Problem Language Result Execution time Memory
1081155 2024-08-29T18:51:48 Z skittles1412 The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 2078 ms 119716 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<>>;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

inline void init_io() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
}

template <typename T>
T reversed(T arr) {
    reverse(begin(arr), end(arr));
    return arr;
}

template <typename T>
vector<vector<T>> transposed(const vector<vector<T>>& arr) {
    int n = sz(arr), m = sz(arr[0]);

    vector ans(m, vector<T>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans[j][i] = arr[i][j];
        }
    }

    return ans;
}

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

inline vector<bool>::reference operator|=(vector<bool>::reference&& a, bool b) {
    a = a | b;
    return a;
}

vector<int> cvals[2];

int grade(const vector<vector<int>>& arr, const vector<int>& lens) {
    int n = sz(arr), m = sz(arr[0]);

    for (auto& a : cvals) {
        a.clear();
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cvals[j >= lens[i]].push_back(arr[i][j]);
        }
    }

    int ans = 0;
    for (auto& a : cvals) {
        if (!sz(a)) {
            continue;
        }
        ans = max(ans, *max_element(begin(a), end(a)) -
                           *min_element(begin(a), end(a)));
    }

    return ans;
}

vector<int> lens;

int solve1(const vector<vector<int>>& arr, int kv) {
    dbg(arr, kv);
    int n = sz(arr), m = sz(arr[0]);

    lens.resize(n);
    fill(begin(lens), end(lens), 0);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] >= kv) {
                lens[i] = j + 1;
            }
        }
    }

    dbg(lens);
    for (int i = n - 2; i >= 0; i--) {
        lens[i] = max(lens[i], lens[i + 1]);
    }

    return grade(arr, lens);
}

int solve1_all(vector<vector<int>> arr, int kv) {
    int ans = 1e9;

    ans = min(ans, solve1(arr, kv));
    ans = min(ans, solve1(reversed(arr), kv));

    for (auto& a : arr) {
        reverse(begin(a), end(a));
    }

    ans = min(ans, solve1(arr, kv));
    ans = min(ans, solve1(reversed(arr), kv));

    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;

    vector arr(n, vector(m, -1));
    for (auto& a : arr) {
        for (auto& b : a) {
            cin >> b;
        }
    }

    int mn = 1e9;
    for (auto& a : arr) {
        for (auto& b : a) {
            mn = min(mn, b);
        }
    }

    auto a1 = arr, a2 = reversed(arr);
    for (auto& a : arr) {
        reverse(begin(a), end(a));
    }
    auto a3 = arr, a4 = reversed(arr);

    auto check = [&](int x) -> bool {
        return solve1(a1, mn + x + 1) <= x || solve1(a2, mn + x + 1) <= x ||
               solve1(a3, mn + x + 1) <= x || solve1(a4, mn + x + 1) <= x;
    };

    int l = 0, r = 1e9;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << l << endl;
}

int main() {
    init_io();
    solve();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 7 ms 1752 KB Output is correct
17 Correct 13 ms 1760 KB Output is correct
18 Correct 17 ms 1760 KB Output is correct
19 Correct 14 ms 1760 KB Output is correct
20 Correct 14 ms 1496 KB Output is correct
21 Correct 25 ms 1760 KB Output is correct
22 Correct 24 ms 1624 KB Output is correct
23 Correct 17 ms 1628 KB Output is correct
24 Correct 24 ms 1496 KB Output is correct
25 Correct 26 ms 1628 KB Output is correct
26 Correct 20 ms 1668 KB Output is correct
27 Correct 26 ms 1844 KB Output is correct
28 Correct 18 ms 1760 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 7 ms 1752 KB Output is correct
17 Correct 13 ms 1760 KB Output is correct
18 Correct 17 ms 1760 KB Output is correct
19 Correct 14 ms 1760 KB Output is correct
20 Correct 14 ms 1496 KB Output is correct
21 Correct 25 ms 1760 KB Output is correct
22 Correct 24 ms 1624 KB Output is correct
23 Correct 17 ms 1628 KB Output is correct
24 Correct 24 ms 1496 KB Output is correct
25 Correct 26 ms 1628 KB Output is correct
26 Correct 20 ms 1668 KB Output is correct
27 Correct 26 ms 1844 KB Output is correct
28 Correct 18 ms 1760 KB Output is correct
29 Correct 1589 ms 115060 KB Output is correct
30 Correct 1205 ms 113148 KB Output is correct
31 Correct 1899 ms 119180 KB Output is correct
32 Correct 1242 ms 119212 KB Output is correct
33 Correct 1314 ms 107692 KB Output is correct
34 Correct 1413 ms 119716 KB Output is correct
35 Correct 2078 ms 110852 KB Output is correct
36 Correct 1559 ms 98236 KB Output is correct
37 Correct 1876 ms 110764 KB Output is correct