Submission #896223

#	Time	Username	Problem	Language	Result	Execution time	Memory
896223		box	Hamburg Steak (JOI20_hamburg)	C++17	1 / 100	72 ms	13112 KiB

hamburg

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

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; bug_h(__VA_ARGS__)
#else
#define cerr if (false) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;

const int INF = 1e9;

int N, K;
vector<ar<int, 4>> rect;
vector<bool> covered;
vector<pi> solutions;

ar<int, 4> get_bounds() {
    int x1 = INF, x2 = 1, y1 = INF, y2 = 1;
    for (int i = 0; i < N; i++) if (!covered[i]) {
        auto [l, d, r, u] = rect[i];
        x1 = min(x1, r);
        x2 = max(x2, l);
        y1 = min(y1, u);
        y2 = max(y2, d);
    }
    return {x1, x2, y1, y2};
}

void pr() {
    for (auto [x, y] : solutions) cout << x << ' ' << y << '\n';
    exit(0);
}

void rec(int k) {
    if (!k) {
        if (count(begin(covered), end(covered), 1) == N) pr();
        return;
    }
    auto [x1, x2, y1, y2] = get_bounds();
    for (auto x : {x1, x2}) for (auto y : {y1, y2}) {
        solutions.push_back({x, y});
        vector<int> add;
        for (int i = 0; i < N; i++) if (!covered[i]) {
            auto [l, d, r, u] = rect[i];
            if (l <= x && x <= r && d <= y && y <= r) add.push_back(i);
        }
        for (int i : add) covered[i] = 1;
        rec(k - 1);
        for (int i : add) covered[i] = 0;
        solutions.pop_back();
    }
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    rect.resize(N);
    for (auto &[l, d, r, u] : rect) {
        cin >> l >> d >> r >> u;
    }
    covered.resize(N);
    rec(K);
}

• Subtask 1: 1 / 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