oj.uz

Submission #518541

# Submission time Handle Problem Language Result Execution time Memory
518541 2022-01-24T04:15:47 Z Giantpizzahead The Kingdom of JOIOI (JOI17_joioi) C++17
60 / 100
 4000 ms 86728 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, 8) {
        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 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 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 0 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 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 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 0 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 1996 KB Output is correct
16 Correct 14 ms 2812 KB Output is correct
17 Correct 33 ms 3016 KB Output is correct
18 Correct 871 ms 3056 KB Output is correct
19 Correct 748 ms 3080 KB Output is correct
20 Correct 208 ms 3016 KB Output is correct
21 Correct 35 ms 3132 KB Output is correct
22 Correct 961 ms 3216 KB Output is correct
23 Correct 682 ms 3120 KB Output is correct
24 Correct 766 ms 3092 KB Output is correct
25 Correct 376 ms 3136 KB Output is correct
26 Correct 35 ms 3136 KB Output is correct
27 Correct 30 ms 3176 KB Output is correct
28 Correct 30 ms 3100 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 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 0 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 1996 KB Output is correct
16 Correct 14 ms 2812 KB Output is correct
17 Correct 33 ms 3016 KB Output is correct
18 Correct 871 ms 3056 KB Output is correct
19 Correct 748 ms 3080 KB Output is correct
20 Correct 208 ms 3016 KB Output is correct
21 Correct 35 ms 3132 KB Output is correct
22 Correct 961 ms 3216 KB Output is correct
23 Correct 682 ms 3120 KB Output is correct
24 Correct 766 ms 3092 KB Output is correct
25 Correct 376 ms 3136 KB Output is correct
26 Correct 35 ms 3136 KB Output is correct
27 Correct 30 ms 3176 KB Output is correct
28 Correct 30 ms 3100 KB Output is correct
29 Execution timed out 4064 ms 86728 KB Time limit exceeded
30 Halted 0 ms 0 KB -