Submission #1307747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307747		M_W_13	Hamburg Steak (JOI20_hamburg)	C++20	2 / 100	85 ms	6692 KiB

hamburg

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
int n, k;
vector<int> A;
vector<int> B;


struct prostokat {
    int l, d, r, u;
};

struct pkt {
    int x, y;
};

bool check(prostokat p, pkt pt) {
    if (pt.x < p.l || pt.x > p.r) return false;
    if (pt.y < p.d || pt.y > p.u) return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    prostokat T[n];
    pii X[n];
    pii Y[n];
    rep(i, n) {
        cin >> T[i].l >> T[i].d >> T[i].r >> T[i].u;
        X[i] = {T[i].l, T[i].r};
        Y[i] = {T[i].d, T[i].u};
    }
    sort(X, X + n);
    sort(Y, Y + n);
    int val = 1e9 + 1;
    for (int i = n - 1; i >= 0; i--) {
        if (val > X[i].nd) {
            A.pb(X[i].st);
            val = X[i].st;
        }
    }
    val = 1e9 + 1;
    for (int i = n - 1; i >= 0; i--) {
        if (val > Y[i].nd) {
            B.pb(Y[i].st);
            val = Y[i].st;
        }
    }
    int szA = A.size();
    int szB = B.size();
    int r = szA * szB;
    int maks = 1 << r;
    rep(maska, maks) {
        bool czy[szA][szB];
        int cnt[szA];
        int cnt2[szB];
        rep(i, szA) {
            cnt[i] = 0;
        }
        rep(i, szB) {
            cnt2[i] = 0;
        }
        int pom = maska;
        int s = 0;
        vector<pkt> vec;
        rep(i, r) {
            if ((pom % 2) == 1) {
                czy[i/szB][i % szB] = true;
                cnt[i/szB]++;
                cnt2[i % szB]++;
                vec.pb({A[i/szB], B[i % szB]});
                s++;
            }
            else {
                czy[i/szB][i % szB] = false;
            }
            pom /= 2;
        }
        bool spr = true;
        rep(i, szA) {
            if (cnt[i] == 0) spr = false;
        }
        rep(i, szB) {
            if (cnt2[i] == 0) spr = false;
        }
        if (s > k) spr = false;
        if (!spr) continue;
        bool czy2 = true;
        rep(i, n) {
            bool c = false;
            for (auto p: vec) {
                if (check(T[i], p)) {
                    c = true;
                    break;
                }
            }
            if (!c) czy2 = false;
        }
        if (czy2) {
            while ((int)vec.size() < k) {
                vec.pb(vec[0]);
            }
            for (auto p: vec) {
                cout << p.x << " " << p.y << '\n';
            }
            break;
        }
    }
    return 0;
}

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