제출 #1197911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197911		rhombus	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	1875 ms	47648 KiB

joioi

#include <bits/stdc++.h>

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 0
#endif

using namespace std;

typedef long long ll;

const int inf = 1e9 + 7;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector a(n, vector (m, 0)); 
    int mx = 0, mn = inf;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }
    }
    int l = 0, r = mx - mn, res = mx - mn;
    while (l <= r) {
        int mid = (l + r) / 2;
        int ub = mn + mid;
        int lb = mx - mid;
        vector c(n, vector (m, 0));
        vector <int> s(n, 0);
        bool bad = false;
        for (int i = 0; i < n; i++) {
            int prev = -1;
            int switches = 0;
            for (int j = 0; j < m; j++) {
                if (a[i][j] > ub && a[i][j] < lb) {
                    bad = true;
                    break;
                }
                if (a[i][j] > ub) {
                    c[i][j] = 2;
                } else if (a[i][j] < lb) {
                    c[i][j] = 1;
                }
                if (c[i][j] != 0) {
                    if (prev != -1 && c[i][j] != prev) {
                        switches++;
                    }
                    prev = c[i][j];
                }
            }
            if (bad) break;
            if (switches >= 2) {
                bad = true;
                break;
            }
            s[i] = switches;
        }
        bool bad1 = false, bad2 = false;
        auto temp = c;
        {
            for (int i = 0; i < n; i++) {
                if (s[i] > 0) {
                    bool first = false;
                    for (int j = 0; j < m; j++) {
                        if (c[i][j] == 2 && !first) bad1 = true;
                        if (c[i][j] == 1) first = true;
                    }
                }
                for (int j = 0; j < m; j++) {
                    if (c[i][j] == 2) {
                        for (int k = j; k < m; k++) {
                            c[i][k] = 2;
                        }
                        break;
                    }
                }
                for (int j = m - 1; j >= 0; j--) {
                    if (c[i][j] == 1) {
                        for (int k = j; k >= 0; k--) {
                            c[i][k] = 1;
                        }
                        break;
                    }
                }
            }
            for (int j = 0; j < m; j++) {
                int prev = -1, switches = 0;
                for (int i = 0; i < n; i++) {
                    if (c[i][j] != 0) {
                        if (prev != -1 && c[i][j] != prev) {
                            switches++;
                        }
                        prev = c[i][j];
                    }
                }
                if (switches >= 2) {
                    bad1 = true;
                }
            }
        }
        c = temp;
        {
            for (int i = 0; i < n; i++) {
                if (s[i] > 0) {
                    bool first = false;
                    for (int j = 0; j < m; j++) {
                        if (c[i][j] == 1 && !first) bad2 = true;
                        if (c[i][j] == 2) first = true;
                    }
                }
                for (int j = 0; j < m; j++) {
                    if (c[i][j] == 1) {
                        for (int k = j; k < m; k++) {
                            c[i][k] = 1;
                        }
                        break;
                    }
                }
                for (int j = m - 1; j >= 0; j--) {
                    if (c[i][j] == 2) {
                        for (int k = j; k >= 0; k--) {
                            c[i][k] = 2;
                        }
                        break;
                    }
                }
            }
            for (int j = 0; j < m; j++) {
                int prev = -1, switches = 0;
                for (int i = 0; i < n; i++) {
                    if (c[i][j] != 0) {
                        if (prev != -1 && c[i][j] != prev) {
                            switches++;
                        }
                        prev = c[i][j];
                    }
                }
                if (switches >= 2) {
                    bad2 = true;
                }
            }
        }
        bad |= (bad1 && bad2);
        if (bad) {
            l = mid + 1;
        } else {
            r = mid - 1;
            res = mid;
        }
    }
    cout << res << '\n';
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40