제출 #1322691

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

joioi

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using pq = priority_queue<T, vector<T>, greater<T>>;
const ll INF = 1e15;
ll MOD = 1e5 + 1;
ll MAXn = 2e6;
ll lg = 22;
const ld ap = 1e-6;
const double pi = acos(-1);
using rc = complex<double>;

template<class T>
istream &operator>>(istream &in, vector<T> &x) {
    for (auto &i : x) {
        in >> i;
    }
    return in;
}

template<class T>
ostream &operator<<(ostream &out, vector<T> &x) {
    for (auto &i : x) {
        out << i << ' ';
    }
    return out;
}

struct el {
    ll x, t, i, j;
};

bool cmp(el a, el b) {
    return a.x > b.x;
}

bool check(ll n, ll m, vector<vector<ll>> is) {
    ll f = max(0ll, is[0][0]);
    is[0][0] = 0;
    ll pr = m;
    for (ll i = 0; i < n; i++) {
        ll lst = -1;
        if (is[i][0] == 0) lst = 0;
        if (is[i][0] == -1) is[i][0] = 0;
        ll cn = is[i][0] == 0;
        for (ll j = 1; j < m; j++) {
            if (is[i][j] == 0) lst = j;
            if (is[i][j] != -1) {
                is[i][j] ^= f;
            } else {
                is[i][j] = is[i][j - 1];
            }
            if (is[i][j - 1] == 1 && is[i][j] == 0) return 0;
            if (is[i][j] == 0) cn++;
        }
        if (lst + 1 > pr) return 0;
        pr = cn;
    }
    return 1;
}

void rotate(ll &n, ll &m, vector<vector<ll>> &is) {
    vector<vector<ll>> res(m, vector<ll>(n));
    for (ll i = 0; i < m; i++) {
        for (ll j = 0; j < n; j++) {
            res[i][j] = is[n - j - 1][i];
        }
    }
    is = res;
    swap(n, m);
}

void viperr() {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> a(n, vector<ll>(m));
    for (auto &i : a) cin >> i;
    deque<pair<ll, pair<ll, ll>>> b;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < m; j++) {
            b.emplace_back(a[i][j], pair<ll, ll>{i, j});
        }
    }
    std::sort(b.begin(), b.end());
    vector<el> c;
    for (ll i = 1; i < b.size() - 1; i++) {
        c.emplace_back(max(b.back().first - b[i].first, b[i].first - b.front().first),
                       b.back().first - b[i].first < b[i].first - b.front().first, b[i].second.first,
                       b[i].second.second);
    }
    std::sort(c.begin(), c.end(), cmp);
    ll l = 0, r = c.size();
    while (r - l > 1) {
        ll x = (r + l) / 2;
        vector<vector<ll>> is(n, vector<ll>(m, -1));
        for (ll i = 0; i <= x; i++) {
            is[c[i].i][c[i].j] = c[i].t;
        }
        bool res = check(n, m, is);
        rotate(n, m, is);
        res |= check(n, m, is);
        rotate(n, m, is);
        res |= check(n, m, is);
        rotate(n, m, is);
        res |= check(n, m, is);
        rotate(n, m, is);
        if (res) l = x;
        else r = x;
    }
    c.emplace_back(0, 0, 0, 0);
    cout << max(c[l + 1].x, b.back().first - b.front().first - c[l].x);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t11 = 1;
//    cin >> t11;
    while (t11--) {
        viperr();
        cout << '\n';
    }
    return 0;
}

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