oj.uz

Submission #518544

# Submission time Handle Problem Language Result Execution time Memory
518544 2022-01-24T04:20:12 Z Giantpizzahead The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 2442 ms 117608 KB 
/*
Solution: 
Runtime: 
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (false) cerr
using ll = long long;

const int INF = 1e9+7;
const int MAXN = 2005;

int H, W, minV = INF, maxV = -INF;
int A[MAXN][MAXN], newA[MAXN][MAXN];
struct Loc {
    int i, j, c;
    bool operator<(const Loc& o) const {
        return c > o.c;
    }
};
vector<Loc> locs;
set<pair<int, int>> boundL, boundR;

int getAns() {
    locs.clear();
    boundL.clear();
    boundR.clear();
    rep(i, 0, H) rep(j, 0, W) locs.push_back({i, j, max(maxV - A[i][j], A[i][j] - minV)});
    sort(all(locs));

    // Place into regions until invalid
    boundL.insert({H, -1});
    boundR.insert({-1, W});
    int ans = INF;
    for (Loc& l : locs) {
        int i = l.i, j = l.j;
        // debug << endl << "place A[" << i << "][" << j << "] = " << A[i][j] << endl;
        if (maxV - A[i][j] == l.c) {
            // Should go along with min (left) region
            auto ptr = prev(boundR.lower_bound({i, INF}));
            if (ptr->second <= j) {
                // Does not work
                ans = l.c;
                break;
            }
            // This works; update left region bound
            ptr = boundL.lower_bound({i, -1});
            if (ptr->second < j) {
                // Update the bound
                while (true) {
                    ptr = boundL.lower_bound({i, INF});
                    if (ptr == boundL.begin()) break;
                    ptr = prev(ptr);
                    if (ptr->second > j) break;
                    boundL.erase(ptr);
                }
                // Place new bound
                boundL.insert({i, j});
            }
            // debug << "left" << endl;
        } else {
            // Should go along with max (right) region
            auto ptr = boundL.lower_bound({i, -1});
            if (ptr->second >= j) {
                // Does not work
                ans = l.c;
                break;
            }
            // This works; update right region bound
            ptr = prev(boundR.lower_bound({i, INF}));
            if (ptr->second > j) {
                // Update the bound
                while (true) {
                    ptr = boundR.lower_bound({i, -1});
                    if (ptr == boundR.end() || ptr->second < j) break;
                    boundR.erase(ptr);
                }
                // Place new bound
                boundR.insert({i, j});
            }
            // debug << "right" << endl;
        }
        ans = min(maxV - A[i][j], A[i][j] - minV);

        // Debug boundaries
        /*
        vector<vector<char>> test(H, vector<char>(W, '.'));
        for (auto& p : boundL) {
            if (p.second == -1) continue;
            test[p.first][p.second] = '1';
        }
        for (auto& p : boundR) {
            if (p.first == -1) continue;
            test[p.first][p.second] = '2';
        }
        rep(i, 0, H) rep(j, 0, W) debug << test[i][j] << " \n"[j==W-1];
        */
    }
    // debug << "ans " << ans << endl;
    return ans;
}

void solve() {
    cin >> H >> W;
    rep(i, 0, H) rep(j, 0, W) {
        cin >> A[i][j];
        minV = min(A[i][j], minV);
        maxV = max(A[i][j], maxV);
    }

    // Try all rotations and flips
    int ans = maxV - minV;
    rep(d, 0, 4) {
        // debug << endl;
        // rep(i, 0, H) rep(j, 0, W) debug << A[i][j] << " \n"[j==W-1];
        int tempAns = getAns();
        // cout << tempAns << '\n';
        ans = min(tempAns, ans);
        if (d != 3) {
            // Rotate board
            // (i, j) -> (j, [new W]-1-i)
            rep(i, 0, H) rep(j, 0, W) newA[j][H-1-i] = A[i][j];
            swap(H, W);
            rep(i, 0, H) rep(j, 0, W) A[i][j] = newA[i][j];
        } else {
            // Flip board
            // (i, j) -> (H-1-i, j)
            // rep(i, 0, H) rep(j, 0, W) newA[H-1-i][j] = A[i][j];
            // rep(i, 0, H) rep(j, 0, W) A[i][j] = newA[i][j];
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 1996 KB Output is correct
16 Correct 8 ms 2756 KB Output is correct
17 Correct 17 ms 2756 KB Output is correct
18 Correct 20 ms 2756 KB Output is correct
19 Correct 19 ms 2756 KB Output is correct
20 Correct 17 ms 2784 KB Output is correct
21 Correct 17 ms 2756 KB Output is correct
22 Correct 20 ms 2756 KB Output is correct
23 Correct 20 ms 2756 KB Output is correct
24 Correct 18 ms 2768 KB Output is correct
25 Correct 18 ms 2756 KB Output is correct
26 Correct 17 ms 2756 KB Output is correct
27 Correct 17 ms 2788 KB Output is correct
28 Correct 17 ms 2748 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 1996 KB Output is correct
16 Correct 8 ms 2756 KB Output is correct
17 Correct 17 ms 2756 KB Output is correct
18 Correct 20 ms 2756 KB Output is correct
19 Correct 19 ms 2756 KB Output is correct
20 Correct 17 ms 2784 KB Output is correct
21 Correct 17 ms 2756 KB Output is correct
22 Correct 20 ms 2756 KB Output is correct
23 Correct 20 ms 2756 KB Output is correct
24 Correct 18 ms 2768 KB Output is correct
25 Correct 18 ms 2756 KB Output is correct
26 Correct 17 ms 2756 KB Output is correct
27 Correct 17 ms 2788 KB Output is correct
28 Correct 17 ms 2748 KB Output is correct
29 Correct 1659 ms 76360 KB Output is correct
30 Correct 1705 ms 75272 KB Output is correct
31 Correct 1998 ms 78748 KB Output is correct
32 Correct 1681 ms 78868 KB Output is correct
33 Correct 2116 ms 72688 KB Output is correct
34 Correct 1941 ms 101992 KB Output is correct
35 Correct 2134 ms 117520 KB Output is correct
36 Correct 2442 ms 106408 KB Output is correct
37 Correct 2293 ms 117608 KB Output is correct