Submission #386582

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

hamburg

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

const int N = 200000, X = 1000000000;

vector<array<int, 2>> skewers;
array<int, 4> rects[N];
bool tested[N];
int n;

array<int, 4> bounds() {
    int x1 = X, x2 = 1, y1 = X, y2 = 1;
    for (int i = 0; i < n; ++i) {
        if (!tested[i]) {
            auto [x3, x4, y3, y4] = rects[i];
            x1 = min(x1, x4);
            x2 = max(x2, x3);
            y1 = min(y1, y4);
            y2 = max(y2, y3);
        }
    }
    return {x1, x2, y1, y2};
}

void solve(int k) {
    if (k == 0) {
        if (count(tested, tested + n, true) == n) {
            for (auto [x, y] : skewers) {
                cout << x << " " << y << "\n";
            }
            exit(0);
        }
        return;
    }

    auto [x1, x2, y1, y2] = bounds();

    for (auto x : {x1, x2}) {
        for (auto y : {y1, y2}) {
            skewers.push_back({x, y});
            vector<int> undo;
            for (int i = 0; i < n; ++i) {
                if (!tested[i]) {
                    auto [x3, x4, y3, y4] = rects[i];
                    if (x3 <= x && x <= x4) {
                        if (y3 <= y && y <= y4) {
                            tested[i] = true;
                            undo.push_back(i);
                        }
                    }
                }
            }

            solve(k - 1);

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

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

    int k;
    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        cin >> rects[i][0] >> rects[i][2] >> rects[i][1] >> rects[i][3];
    }

    solve(k);

    cout << -1 << "\n";
}

• 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