Submission #886589

#	Time	Username	Problem	Language	Result	Execution time	Memory
886589		vjudge1	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	1480 ms	171976 KiB

hamburg

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

const int N = 2e5 + 10;
const int inf = 1e9 + 10;

int n, k;
int l[N], r[N], u[N], d[N];

namespace brute {

vector<pair<int, int>> point;
int done[N];

void dfs(int step) {
        int minR = inf, maxL = -1, minU = inf, maxD = -1;
        for (int i = 0; i < n; i++) {
                if (done[i]) continue;
                minR = min(minR, r[i]);
                maxL = max(maxL, l[i]);
                minU = min(minU, u[i]);
                maxD = max(maxD, d[i]);
        }

        if (maxL == -1) {
                for (auto [x, y] : point) cout << x << ' ' << y << '\n';
                for (int i = point.size(); i < k; i++) cout << "1 1\n";
                exit(0);
        }

        if (step == k) return;

        for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                        int x = i ? minR : maxL;
                        int y = j ? minU : maxD;
                        point.emplace_back(x, y);
                        vector<int> del;
                        for (int p = 0; p < n; p++) {
                                if (done[p]) continue;
                                if (l[p] <= x && x <= r[p] && d[p] <= y && y <= u[p]) {
                                        done[p] = 1;
                                        del.emplace_back(p);
                                }
                        }
                        dfs(step + 1);
                        for (int p : del) done[p] = 0;
                        point.pop_back();
                }
        }
}

};  // namespace brute

namespace two_sat {

int timer = 0;
int id[N][2];
const int C = 6;
vector<int> G[N * C];
vector<int> R[N * C];
int to[N], from[N];
int good[N];
int mask[N];
int LL, RR, DD, UU;

void init() {
        int minR = inf, maxL = -1, minU = inf, maxD = -1;
        for (int i = 0; i < n; i++) {
                minR = min(minR, r[i]);
                maxL = max(maxL, l[i]);
                minU = min(minU, u[i]);
                maxD = max(maxD, d[i]);
        }

        assert(minR <= maxL && minU <= maxD);

        LL = minR, RR = maxL, UU = maxD, DD = minU;

        vector<vector<pair<int, int>>> ranges(4);

        for (int i = 0; i < n; i++) {
                if (l[i] <= LL && LL <= r[i]) mask[i] ^= 1;
                if (l[i] <= RR && RR <= r[i]) mask[i] ^= 2;
                if (d[i] <= DD && DD <= u[i]) mask[i] ^= 4;
                if (d[i] <= UU && UU <= u[i]) mask[i] ^= 8;

                if (__builtin_popcount(mask[i]) > 2) continue;
                good[i] = 1;

                id[i][0] = timer++, id[i][1] = timer++;  // 2
                                                         // 0: must in that range, 1: vice versa

                if (__builtin_popcount(mask[i]) == 1) {
                        G[id[i][1]].emplace_back(id[i][0]);  // must in that range
                }
                int p = 0;
                for (int j = 0; j < 4; j++) {
                        if (mask[i] >> j & 1) ranges[j].emplace_back(i, p++);
                }
                assert(p > 0);
        }

        auto solve = [&](vector<pair<int, int>>& ord, int x) {
                auto& a = x < 2 ? d : l;
                auto& b = x < 2 ? u : r;

                sort(ord.begin(), ord.end(), [&](auto x, auto y) {
                        return b[x.first] < b[y.first];
                });

                int m = ord.size();
                for (int i = 0; i < m; i++) {
                        to[i] = timer++, from[i] = timer++;  // 2
                        int p = ord[i].second;
                        G[to[i]].emplace_back(id[ord[i].first][p] ^ 1);
                        G[id[ord[i].first][p]].emplace_back(from[i]);
                        if (i > 0) {
                                G[to[i]].emplace_back(to[i - 1]);
                                G[from[i - 1]].emplace_back(from[i]);
                        }
                }

                vector<int> sorted_b(m);
                for (int i = 0; i < m; i++) sorted_b[i] = b[ord[i].first];

                for (auto [i, p] : ord) {
                        int j = lower_bound(sorted_b.begin(), sorted_b.end(), a[i]) - sorted_b.begin() - 1;
                        if (j >= 0) {
                                G[id[i][p]].emplace_back(to[j]);
                                G[from[j]].emplace_back(id[i][p] ^ 1);
                        }
                }
        };
        for (int i = 0; i < 4; i++) solve(ranges[i], i);

        assert(timer < N * C);
}

vector<int> topo;
int done[N * C];
int comp[N * C];

void dfs(int u) {
        done[u] = 1;
        for (int v : G[u]) {
                if (!done[v]) dfs(v);
        }
        topo.emplace_back(u);
}

void scc(int u, int id) {
        done[u] = 0;
        comp[u] = id;
        for (int v : R[u]) {
                if (done[v]) scc(v, id);
        }
}

void solve() {
        for (int i = 0; i < timer; i++) {
                for (int j : G[i]) R[j].emplace_back(i);
        }

        for (int i = 0; i < timer; i++) {
                if (!done[i]) dfs(i);
        }

        reverse(topo.begin(), topo.end());

        int P = 0;
        for (int i : topo) {
                if (done[i]) scc(i, P++);
        }

        vector<pair<int, int>> point(4);
        point[0].first = LL, point[1].first = RR;
        point[2].second = DD, point[3].second = UU;

        for (int i = 0; i < n; i++) {
                if (!good[i]) continue;
                int which = comp[id[i][0]] < comp[id[i][1]];
                int j = 0, p = 0;
                for (j = 0; j < 4; j++) {
                        if (mask[i] >> j & 1) {
                                if (p++ == which) break;
                        }
                }
                auto& x = (j < 2) ? (j == 0 ? point[0].second : point[1].second)
                                  : (j == 2 ? point[2].first : point[3].first);
                auto& a = j < 2 ? d : l;

                x = max(x, a[i]);
        }

        for (int i = 0; i < 4; i++) {
                auto [x, y] = point[i];
                cout << x << ' ' << y << '\n';
        }
}
};  // namespace two_sat

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> l[i] >> d[i] >> r[i] >> u[i];

        brute::dfs(0);

        two_sat::init();
        two_sat::solve();
}

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