Submission #1137508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137508		_8_8_	Hamburg Steak (JOI20_hamburg)	C++20	0 / 100	4 ms	328 KiB

hamburg

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;

const int N = (int)1e6 + 12, MOD = 998244353, inf = (int)1e9 + 1;

int n, k;
array<int, 4> a[N];
bool cmp(array<int, 4> x, array<int, 4> y) {
    if(make_pair(x[0], x[1]) == make_pair(y[0], y[1])) {
        if(x[3] != y[3]) {
            return x[3] < y[3];
        }
        return x[2] < y[2];
    }
    if(x[1] != y[1]) {
        return x[1] < y[1];
    }
    return x[0] < y[0];
}
vector<array<int, 4>> ans;
bool can(int l, int r, bool v) {
    if(l > r) return true;
    int mn = inf, mx = -inf;
    for(int i = l; i <= r; i++) {
        mn = min(mn, a[i][1]);
        mx = max(mx, a[i][0]);
    }
    array<int, 4> res;
    if(mx > mn) return 0;
    res[0] = mx;
    res[1] = mn;
    mx = -inf, mn = inf;
    for(int i = l; i <= r; i++) {
        mn = min(mn, a[i][3]);
        mx = max(mx, a[i][2]);
    }
    if(mx > mn) return 0;
    res[2] = mx;
    res[3] = mn;
    if(v) {
        ans.push_back(res);
    }
    return true;
}
bool check(int l, int r, bool v) {
    if(l > r) return true;
    for(int i = l; i <= r; i++) {
        if(can(l, i, 0) && can(i + 1, r, 0))  {
            if(v) {
                can(l, i, 1);
                can(i + 1, r, 1);
            }
            return true;
        } 
    }
    return false;
}
void test() {
    cin >> n >> k;
    if(k != 2) return;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i][0] >> a[i][2] >> a[i][1] >> a[i][3];
    }
    sort(a + 1, a + n + 1, cmp);
    int l = 1, r = n + 1;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(check(1, mid, 0)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    check(1, l, 1);
    check(l + 1, n, 1);
    assert(l ==n);
    while((int)ans.size() < k) {
        ans.push_back(ans.back());
    }
    for(auto [l, r, u, d] : ans) {
        cout << l << ' ' << u << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t = 1;
    // cin >> t;

    while(t--) {
        test();
    }
}

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