Submission #518540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
518540	2022-01-24T04:15:36 Z	Giantpizzahead	The Kingdom of JOIOI (JOI17_joioi)	Java 11	Compilation error	0 ms	0 KB

joioi

/*
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;
}

Compilation message

joioi.java:6: error: illegal character: '#'
#include <bits/stdc++.h>
^
joioi.java:6: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
joioi.java:8: error: illegal character: '#'
#define rep(i, a, b) for (int i = (a); i < (b); i++)
^
joioi.java:8: error: class, interface, or enum expected
#define rep(i, a, b) for (int i = (a); i < (b); i++)
        ^
joioi.java:8: error: class, interface, or enum expected
#define rep(i, a, b) for (int i = (a); i < (b); i++)
                                       ^
joioi.java:8: error: class, interface, or enum expected
#define rep(i, a, b) for (int i = (a); i < (b); i++)
                                                ^
joioi.java:9: error: illegal character: '#'
#define sz(x) ((int) x.size())
^
joioi.java:10: error: illegal character: '#'
#define all(x) x.begin(), x.end()
^
joioi.java:11: error: illegal character: '#'
#define debug if (false) cerr
^
joioi.java:14: error: class, interface, or enum expected
const int INF = 1e9+7;
^
joioi.java:15: error: class, interface, or enum expected
const int MAXN = 2005;
^
joioi.java:17: error: class, interface, or enum expected
int H, W, minV = INF, maxV = -INF;
^
joioi.java:18: error: class, interface, or enum expected
int A[MAXN][MAXN], newA[MAXN][MAXN];
^
joioi.java:19: error: class, interface, or enum expected
struct Loc {
^
joioi.java:21: error: class, interface, or enum expected
    bool operator<(const Loc& o) const {
    ^
joioi.java:23: error: class, interface, or enum expected
    }
    ^
joioi.java:25: error: class, interface, or enum expected
vector<Loc> locs;
^
joioi.java:26: error: class, interface, or enum expected
set<pair<int, int>> boundL, boundR;
^
joioi.java:28: error: class, interface, or enum expected
int getAns() {
^
joioi.java:30: error: class, interface, or enum expected
    boundL.clear();
    ^
joioi.java:31: error: class, interface, or enum expected
    boundR.clear();
    ^
joioi.java:32: error: class, interface, or enum expected
    rep(i, 0, H) rep(j, 0, W) locs.push_back({i, j, max(maxV - A[i][j], A[i][j] - minV)});
    ^
joioi.java:33: error: class, interface, or enum expected
    sort(all(locs));
    ^
joioi.java:36: error: class, interface, or enum expected
    boundL.insert({H, -1});
    ^
joioi.java:37: error: class, interface, or enum expected
    boundR.insert({-1, W});
    ^
joioi.java:38: error: class, interface, or enum expected
    int ans = INF;
    ^
joioi.java:39: error: class, interface, or enum expected
    for (Loc& l : locs) {
    ^
joioi.java:41: error: class, interface, or enum expected
        debug << endl << "place A[" << i << "][" << j << "] = " << A[i][j] << endl;
        ^
joioi.java:42: error: class, interface, or enum expected
        if (maxV - A[i][j] == l.c) {
        ^
joioi.java:45: error: class, interface, or enum expected
            if (ptr->second <= j) {
            ^
joioi.java:48: error: class, interface, or enum expected
                break;
                ^
joioi.java:49: error: class, interface, or enum expected
            }
            ^
joioi.java:52: error: class, interface, or enum expected
            if (ptr->second < j) {
            ^
joioi.java:56: error: class, interface, or enum expected
                    if (ptr == boundL.begin()) break;
                    ^
joioi.java:57: error: class, interface, or enum expected
                    ptr = prev(ptr);
                    ^
joioi.java:58: error: class, interface, or enum expected
                    if (ptr->second > j) break;
                    ^
joioi.java:59: error: class, interface, or enum expected
                    boundL.erase(ptr);
                    ^
joioi.java:60: error: class, interface, or enum expected
                }
                ^
joioi.java:63: error: class, interface, or enum expected
            }
            ^
joioi.java:65: error: class, interface, or enum expected
        } else {
        ^
joioi.java:68: error: class, interface, or enum expected
            if (ptr->second >= j) {
            ^
joioi.java:71: error: class, interface, or enum expected
                break;
                ^
joioi.java:72: error: class, interface, or enum expected
            }
            ^
joioi.java:75: error: class, interface, or enum expected
            if (ptr->second > j) {
            ^
joioi.java:79: error: class, interface, or enum expected
                    if (ptr == boundR.end() || ptr->second < j) break;
                    ^
joioi.java:80: error: class, interface, or enum expected
                    boundR.erase(ptr);
                    ^
joioi.java:81: error: class, interface, or enum expected
                }
                ^
joioi.java:84: error: class, interface, or enum expected
            }
            ^
joioi.java:86: error: class, interface, or enum expected
        }
        ^
joioi.java:90: error: class, interface, or enum expected
        vector<vector<char>> test(H, vector<char>(W, '.'));
        ^
joioi.java:91: error: class, interface, or enum expected
        for (auto& p : boundL) {
        ^
joioi.java:93: error: class, interface, or enum expected
            test[p.first][p.second] = '1';
            ^
joioi.java:94: error: class, interface, or enum expected
        }
        ^
joioi.java:97: error: class, interface, or enum expected
            test[p.first][p.second] = '2';
            ^
joioi.java:98: error: class, interface, or enum expected
        }
        ^
joioi.java:100: error: class, interface, or enum expected
    }
    ^
joioi.java:102: error: class, interface, or enum expected
    return ans;
    ^
joioi.java:103: error: class, interface, or enum expected
}
^
joioi.java:107: error: class, interface, or enum expected
    rep(i, 0, H) rep(j, 0, W) {
    ^
joioi.java:109: error: class, interface, or enum expected
        minV = min(A[i][j], minV);
        ^
joioi.java:110: error: class, interface, or enum expected
        maxV = max(A[i][j], maxV);
        ^
joioi.java:111: error: class, interface, or enum expected
    }
    ^
joioi.java:115: error: class, interface, or enum expected
    rep(d, 0, 8) {
    ^
joioi.java:117: error: class, interface, or enum expected
        rep(i, 0, H) rep(j, 0, W) debug << A[i][j] << " \n"[j==W-1];
        ^
joioi.java:118: error: class, interface, or enum expected
        int tempAns = getAns();
        ^
joioi.java:120: error: class, interface, or enum expected
        ans = min(tempAns, ans);
        ^
joioi.java:121: error: class, interface, or enum expected
        if (d != 3) {
        ^
joioi.java:125: error: class, interface, or enum expected
            swap(H, W);
            ^
joioi.java:126: error: class, interface, or enum expected
            rep(i, 0, H) rep(j, 0, W) A[i][j] = newA[i][j];
            ^
joioi.java:127: error: class, interface, or enum expected
        } else {
        ^
joioi.java:131: error: class, interface, or enum expected
            rep(i, 0, H) rep(j, 0, W) A[i][j] = newA[i][j];
            ^
joioi.java:132: error: class, interface, or enum expected
        }
        ^
joioi.java:135: error: class, interface, or enum expected
}
^
joioi.java:139: error: class, interface, or enum expected
    cin.tie(0);
    ^
joioi.java:140: error: class, interface, or enum expected
    solve();
    ^
joioi.java:141: error: class, interface, or enum expected
    return 0;
    ^
joioi.java:142: error: class, interface, or enum expected
}
^
77 errors