Submission #886512

#	Time	Username	Problem	Language	Result	Execution time	Memory
886512		vjudge1	함박 스테이크 (JOI20_hamburg)	C++17	15 / 100	231 ms	13520 KiB

hamburg

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

const int N = 2e5 + 10;
const int inf = 1e9 + 10;

int n, k;
int l[N], r[N], u[N], d[N];

namespace brute {

vector<pair<int, int>> point;
int done[N];

void dfs(int step) {
        int minR = inf, maxL = -1, minU = inf, maxD = -1;
        for (int i = 0; i < n; i++) {
                if (done[i]) continue;
                minR = min(minR, r[i]);
                maxL = max(maxL, l[i]);
                minU = min(minU, u[i]);
                maxD = max(maxD, d[i]);
        }

        if (maxL == -1) {
                for (auto [x, y] : point) cout << x << ' ' << y << '\n';
                for (int i = point.size(); i < k; i++) cout << "1 1\n";
                exit(0);
        }

        if (step == k) return;

        for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                        int x = i ? minR : maxL;
                        int y = j ? minU : maxD;
                        point.emplace_back(x, y);
                        vector<int> del;
                        for (int p = 0; p < n; p++) {
                                if (done[p]) continue;
                                if (l[p] <= x && x <= r[p] && d[p] <= y && y <= u[p]) {
                                        done[p] = 1;
                                        del.emplace_back(p);
                                }
                        }
                        dfs(step + 1);
                        for (int p : del) done[p] = 0;
                        point.pop_back();
                }
        }
}

};  // namespace brute

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> l[i] >> d[i] >> r[i] >> u[i];

        brute::dfs(0);
}

• 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