Submission #894730

#	Time	Username	Problem	Language	Result	Execution time	Memory
894730		box	Hamburg Steak (JOI20_hamburg)	C++17	6 / 100	3052 ms	12344 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];
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])};
}
 
mt19937 rng(1234);
 
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));
    */
    while (1) {
        for (int i = 0; i < N; i++) swap(order[i], order[rng() % (i + 1)]);
        fill(done, done + N, false);
        int i = 0;
        for (int rep = 0; rep < K; rep++) {
            while (i < N && done[i]) i++;
            if (i == N) {
                while (rep < K)
                    solutions[rep++] = {1, 1};
                break;
            }
            done[i] = 1;
            auto v = V[order[i]];
            for (int j = i + 1; j < N; j++) if (!done[j] && (v + V[order[j]])[0] != -1) {
                v = v + V[order[j]];
                done[j] = 1;
            }
            solutions[rep] = {v[0], v[2]};
        }
        if (!count(done, done + N, false)) {
            for (int i = 0; i < K; i++)
                cout << solutions[i][0] << " " << solutions[i][1] << '\n';
            break;
        }
    }
}

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