Submission #1306418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306418		Double_Slash	Hamburg Steak (JOI20_hamburg)	C++20	6 / 100	3111 ms	399696 KiB

hamburg

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using Rect = array<int, 4>;

const int INF = 1e9;

int main() {
    int n, k;
    cin >> n >> k;
    vector<Rect> rects(n);
    for (auto &[l, d, r, u]: rects) cin >> l >> d >> r >> u;
    shuffle(all(rects), mt19937(chrono::high_resolution_clock::now().time_since_epoch().count()));
    vector<vector<Rect>> v{{rects.back()}};
    rects.pop_back();
    for (auto &[L, D, R, U]: rects) {
        vector<vector<Rect>> v2;
        for (const auto &s: v) {
            for (int i = s.size(); i--;) {
                auto s2 = s;
                auto &r = s2[i];
                r[0] = max(r[0], L);
                r[2] = min(r[2], R);
                if (r[0] > r[2]) continue;
                r[1] = max(r[1], D);
                r[3] = min(r[3], U);
                if (r[1] > r[3]) continue;
                sort(all(s2));
                v2.push_back(s2);
            }
            if (s.size() == k) continue;
            auto s2 = s;
            s2.push_back({L, D, R, U});
            sort(all(s2));
            v2.push_back(s2);
        }
        v = move(v2);
        sort(all(v));
        v.erase(unique(all(v)), v.end());
    }
    while (v[0].size() < k) v[0].push_back({1, 1, 0, 0});
    for (auto &[l, d, r, u]: v[0]) cout << l << ' ' << d << endl;
}

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