Submission #384645

#	Time	Username	Problem	Language	Result	Execution time	Memory
384645		timmyfeng	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	231 ms	13004 KiB

hamburg

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

const int N = 200000, X = 1000000000;

vector<array<int, 2>> ans;
array<int, 4> rect[N];
bool tested[N];
int n, k;

void print() {
    while ((int) ans.size() < k) {
        ans.push_back(ans.back());
    }
    for (auto [x, y] : ans) {
        cout << x << " " << y << "\n";
    }
    exit(0);
}

void solve() {
    if (count(tested, tested + n, false) == 0) {
        while ((int) ans.size() < k) {
            ans.push_back(ans.back());
        }
        for (auto [x, y] : ans) {
            cout << x << " " << y << "\n";
        }
        exit(0);
    } else if ((int) ans.size() == k) {
        return;
    }

    int x1 = X, x2 = 0, y1 = X, y2 = 0;
    for (int i = 0; i < n; ++i) {
        auto [l, d, r, u] = rect[i];
        if (!tested[i]) {
            x1 = min(x1, r);
            x2 = max(x2, l);
            y1 = min(y1, u);
            y2 = max(y2, d);
        }
    }

    for (auto x : {x1, x2}) {
        for (auto y : {y1, y2}) {
            ans.push_back({x, y});
            vector<int> undo;
            for (int i = 0; i < n; ++i) {
                auto [l, d, r, u] = rect[i];
                if (!tested[i] && l <= x && x <= r && d <= y && y <= u) {
                    undo.push_back(i);
                    tested[i] = true;
                }
            }

            solve();

            for (auto i : undo) {
                tested[i] = false;
            }
            ans.pop_back();
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        for (auto &j : rect[i]) {
            cin >> j;
        }
    }

    solve();
}

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