제출 #1137087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137087		RaresFelix	함박 스테이크 (JOI20_hamburg)	C++20	21 / 100	3088 ms	31796 KiB

hamburg

#include <bits/stdc++.h>

using namespace std;

//#define int ll

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
using vll = vector<ll>;

const int INF = 1e9 + 71;

struct steak {
    ii h, v;
    bool inside(ii pct) {
        return h.first <= pct.first && pct.first <= h.second
            && v.first <= pct.second && pct.second <= v.second;
    }
};

ii seg_extremums(vector<ii> V) {
    int l = -INF, r = INF;
    for(auto [s, d] : V) {
        l = max(l, s);
        r = min(r, d);
    }
    return {l, r};
}

tuple<int, int, int, int> get_steak_extremums(vector<steak> S) {
    vector<ii> H, V;
    for(auto [h, v] : S) {
        H.push_back(h); V.push_back(v);
    }
    auto [lh, rh] = seg_extremums(H);
    auto [lv, rv] = seg_extremums(V);
    return {lh, rh, lv, rv};
}

vector<ii> sol_k2(vector<steak> S) {
    ///will return the solution if it satisfies everyone
    auto [lh, rh, lv, rv] = get_steak_extremums(S);

    vector<ii> re;
    auto check_sol = [&](ii p1, ii p2) -> bool{
        bool ok = true;
        for(auto it : S) {
            ok &= it.inside(p1) || it.inside(p2);
            if(!ok) break;
        }
        if(ok) {
            re = vector<ii>{p1, p2};
        }
        return ok;
    };
    check_sol(ii{lh, lv}, ii{rh, rv});
    check_sol(ii{lh, rv}, ii{rh, lv});
    return re;
}

vector<ii> sol_k1(vector<steak> S) {
    auto [lh, rh, lv, rv] = get_steak_extremums(S);
    if(lh <= rh && lv <= rv) return vector<ii>{ii{lh, lv}};
    return vector<ii>();
}

vector<ii> sol_k3(vector<steak> S) {
    ///will return the solution if it satisfies everyone
    auto [lh, rh, lv, rv] = get_steak_extremums(S);

    vector<ii> Re;
    auto check_rest = [&](ii p) {
        vector<steak> LeftOver;
        for(auto it : S)
            if(!it.inside(p)) LeftOver.push_back(it);
        auto Cur = sol_k2(LeftOver);
        if(!Cur.empty()) {
            Cur.push_back(p);
            Re = Cur;
        }
    };
    check_rest({lh, lv});
    check_rest({lh, rv});
    check_rest({rh, lv});
    check_rest({rh, rv});
    return Re;
}

vector<ii> sol_k4(vector<steak> S) {
    ///will return the solution if it satisfies everyone
    auto [lh, rh, lv, rv] = get_steak_extremums(S);

    vi X, Y;

    for(auto [h, v] : S){
        auto [x1, x2] = h; auto [y1, y2] = v;
        X.push_back(x1); X.push_back(x2);
        Y.push_back(y1); Y.push_back(y2);
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());

    X.resize(unique(X.begin(), X.end()) - X.begin());
    Y.resize(unique(Y.begin(), Y.end()) - Y.begin());

    vector<ii> Re;

    auto check_rest = [&](ii p) {
        vector<steak> LeftOver;
        for(auto it : S)
            if(!it.inside(p)) LeftOver.push_back(it);
        auto Cur = sol_k3(LeftOver);
        if(!Cur.empty()) {
            Cur.push_back(p);
            Re = Cur;
        }
    };
    for(auto y : Y) {
        check_rest({lh, y});
        check_rest({rh, y});
    }
    for(auto x : X) {
        check_rest({x, lv});
        check_rest({x, rv});
    }
    return Re;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    vector<steak> S(n);
    for(int i = 0; i < n; ++i) {
        cin >> S[i].h.first >> S[i].v.first >> S[i].h.second >> S[i].v.second;
    }
    vector<ii> Re;
    if(k == 1) Re = sol_k1(S);
    if(k == 2) Re = sol_k2(S);
    if(k == 3) Re = sol_k3(S);
    if(k == 4) Re = sol_k4(S);

    for(auto it : Re) cout << it.first << " " << it.second << "\n";

    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79