제출 #384657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384657		timmyfeng	함박 스테이크 (JOI20_hamburg)	C++17	15 / 100	233 ms	15180 KiB

hamburg

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

const int N = 200000, X = 1000000000;

vector<array<int, 2>> ans;
array<int, 4> rect[N];
bool tested[N];
int n, k;

vector<int> adj[N], jda[N], order;
int color[N], s, m;
bool visited[N];

void add_expr(int u, int v) {
    adj[u ^ 1].push_back(v);
    adj[v ^ 1].push_back(u);
    jda[u].push_back(v ^ 1);
    jda[v].push_back(u ^ 1);
}

struct side {
    map<int, int> mapping, prefix, suffix;

    void add(int x) {
        if (mapping.count(x) == 0) {
            suffix[x] = m + 4;
            prefix[x] = m + 2;
            mapping[x] = m;
            m += 6;
        }
    }

    int less(int x) {
        add(x);
        return prefix[x];
    }

    int greater(int x) {
        add(x);
        return suffix[x];
    }

    void init() {
        vector<pair<int, int>> pairs(mapping.begin(), mapping.end());
        for (int i = 1; i < (int) pairs.size(); ++i) {
            int x = pairs[i - 1].first, y = pairs[i].first;
            add_expr(prefix[x] ^ 1, suffix[y] ^ 1);
            add_expr(prefix[x] ^ 1, mapping[y] ^ 1);
            add_expr(mapping[x] ^ 1, suffix[y] ^ 1);
        }
    }

    int find() {
        for (auto [x, y] : mapping) {
            if (color[y] > color[y + 1]) {
                return x;
            }
        }
        return -1;
    }
};

array<int, 4> bounds() {
    int x1 = X, x2 = 0, y1 = X, y2 = 0;
    for (int i = 0; i < n; ++i) {
        auto [l, d, r, u] = rect[i];
        if (!tested[i]) {
            x1 = min(x1, r);
            x2 = max(x2, l);
            y1 = min(y1, u);
            y2 = max(y2, d);
        }
    }
    return {x1, x2, y1, y2};
}

void solve() {
    if (count(tested, tested + n, false) == 0) {
        while ((int) ans.size() < k) {
            ans.push_back(ans.back());
        }
        for (auto [x, y] : ans) {
            cout << x << " " << y << "\n";
        }
        exit(0);
    } else if ((int) ans.size() == k) {
        return;
    }

    auto [x1, x2, y1, y2] = bounds();

    for (auto x : {x1, x2}) {
        for (auto y : {y1, y2}) {
            ans.push_back({x, y});
            vector<int> undo;
            for (int i = 0; i < n; ++i) {
                auto [l, d, r, u] = rect[i];
                if (!tested[i] && l <= x && x <= r && d <= y && y <= u) {
                    undo.push_back(i);
                    tested[i] = true;
                }
            }

            solve();

            for (auto i : undo) {
                tested[i] = false;
            }
            ans.pop_back();
        }
    }
}

void dfs_order(int u) {
    visited[u] = true;
    for (auto c : adj[u]) {
        if (!visited[c]) {
            dfs_order(c);
        }
    }
    order.push_back(u);
}

void dfs_color(int u, int x) {
    color[u] = x;
    for (auto c : jda[u]) {
        if (color[c] != 0) {
            dfs_color(c, x);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        for (auto &j : rect[i]) {
            cin >> j;
        }
    }

    solve();

    auto [x1, x2, y1, y2] = bounds();
    side left, down, right, up;

    for (int i = 0; i < n; ++i) {
        auto [l, d, r, u] = rect[i];
        if (!(l <= x1 && x2 <= r) && !(d <= y1 && y2 <= u)) {
            if (l <= x1 && d <= y1) {
                add_expr(left.less(u), down.less(r));
            } else if (l <= x1 && u >= y2) {
                add_expr(left.greater(d), up.less(r));
            } else if (r >= x2 && d <= y1) {
                add_expr(right.less(u), down.greater(l));
            } else if (r >= x2 && u >= y2) {
                add_expr(right.greater(d), up.greater(l));
            } else if (l <= x1) {
                add_expr(left.greater(d), left.greater(d));
                add_expr(left.less(u), left.less(u));
            } else if (r >= x2) {
                add_expr(right.greater(d), right.greater(d));
                add_expr(right.less(u), right.less(u));
            } else if (d <= y1) {
                add_expr(down.greater(l), down.greater(l));
                add_expr(down.less(r), down.less(r));
            } else if (u >= y2) {
                add_expr(up.greater(l), up.greater(l));
                add_expr(up.less(r), up.less(r));
            }
        }
    }

    left.init();
    down.init();
    right.init();
    up.init();

    for (int i = 0; i < m; ++i) {
        if (!visited[i]) {
            dfs_order(i);
        }
    }

    reverse(order.begin(), order.end());
    for (auto i : order) {
        if (color[i] == 0) {
            dfs_color(i, ++s);
        }
    }

    cout << x1 << " " << left.find() << "\n";
    cout << down.find() << " " << y1 << "\n";
    cout << x2 << " " << right.find() << "\n";
    cout << up.find() << " " << y2 << "\n";
}

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