Submission #894733

#	Time	Username	Problem	Language	Result	Execution time	Memory
894733		box	Hamburg Steak (JOI20_hamburg)	C++17	2 / 100	3044 ms	5312 KiB

hamburg

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int MAXN = 2e5;

int N, K;
// int L[MAXN], R[MAXN], U[MAXN], D[MAXN];
ar<int, 4> V[MAXN];
int order[MAXN], __[MAXN];
vector<int> breaks;
bool done[MAXN];
// vector<int> X, Y;
ar<int, 2> solutions[4];

ar<int, 4> operator+(const ar<int, 4> one, const ar<int, 4> two) {
    if (one[0] == -1 || two[0] == -1 || max(one[0], two[0]) > min(one[1], two[1]) || max(one[2], two[2]) > min(one[3], two[3])) return {-1, -1, -1, -1};
    return {max(one[0], two[0]), min(one[1], two[1]), max(one[2], two[2]), min(one[3], two[3])};
}

i64 area(const ar<int, 4> a) {
    return i64(a[1] - a[0] + 1) * i64(a[3] - a[2] + 1);
}

mt19937 rng(1234);

void shuf(int *a, int n) {
    for (int i = 0; i < n; i++) swap(a[i], a[rng() % (i + 1)]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        int l, r, u, d;
        cin >> l >> d >> r >> u;
        V[i] = {l, r, d, u};
        // cin >> L[i] >> R[i] >> U[i] >> D[i];
        /*
        X.push_back(L[i]);
        X.push_back(R[i]);
        Y.push_back(U[i]);
        Y.push_back(D[i]);
        */
        order[i] = i;
    }
    /*
    sort(begin(X), end(X));
    X.erase(unique(begin(X), end(X)), end(X));
    sort(begin(Y), end(Y));
    Y.erase(unique(begin(Y), end(Y)), end(Y));
    */
    for (int i = 0; i < N; i++) swap(order[i], order[rng() % (i + 1)]);
    while (1) {
        fill(done, done + N, false);
        static ar<int, 4> C[4];
        for (int i = 0; i < min(K, N); i++)
            done[i] = true, C[i] = V[order[i]];
        for (int i = N; i < K; i++)
            C[i] = {1, 1, 1, 1};
        for (int i = K; i < N; i++) {
            pair<i64, int> best;
            best.first = -1;
            for (int j = 0; j < K; j++) {
                auto t = C[j] + V[order[i]];
                if (t[0] != -1) {
                    best = max(best, {area(t), j});
                }
            }
            if (~best.first) {
                done[i] = 1;
                C[best.second] = C[best.second] + V[order[i]];
            }
        }
        if (!count(done, done + N, false)) {
            for (int i = 0; i < K; i++)
                cout << C[i][0] << " " << C[i][2] << '\n';
            break;
        } else {
            int s = 0;
            for (int i = 0; i < N; i++) if (!done[i]) __[s++] = order[i];
            int s_ = s;
            for (int i = 0; i < N; i++) if (done[i]) __[s++] = order[i];
            swap(order, __);
            shuf(order, s_);
            shuf(order + s_, s - s_);
        }
    }
}

• 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