Submission #898773

#	Time	Username	Problem	Language	Result	Execution time	Memory
898773		box	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	1356 ms	181872 KiB

hamburg

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

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;

int N;

struct SCC {
    vector<vi> g, rg;
    vi order, id;
    SCC(int n) : g(n), rg(n), id(n) {}
    void make_edge(int i, int j) {
        g.at(i).push_back(j);
        rg.at(j).push_back(i);
    }
    void dfs1(int i) {
        id[i] = 1;
        for (int j : g[i]) if (!id[j]) dfs1(j);
        order.push_back(i);
    }
    void dfs2(int i, int c) {
        id[i] = c;
        for (int j : rg[i]) if (id[j] == -1) dfs2(j, c);
    }
    void solve() {
        for (int i = 0; i < sz(id); i++) if (!id[i]) dfs1(i);
        reverse(all(order)), fill(all(id), -1);
        int c = 0;
        for (int i : order) if (id[i] == -1) dfs2(i, c++);
    }
};

const int INF = 1e9;

int K;
vector<ar<int, 4>> rect;
vector<bool> covered;
vector<pi> solutions;
 
ar<int, 4> get_bounds() {
    int x1 = INF, x2 = 1, y1 = INF, y2 = 1;
    for (int i = 0; i < N; i++) if (!covered[i]) {
        auto [l, d, r, u] = rect[i];
        x1 = min(x1, r);
        x2 = max(x2, l);
        y1 = min(y1, u);
        y2 = max(y2, d);
    }
    return {x1, x2, y1, y2};
}
 
void pr() {
    for (auto [x, y] : solutions) cout << x << ' ' << y << '\n';
    exit(0);
}
 
void rec(int k) {
    if (!k) {
        if (count(all(covered), 1) == N) pr();
        return;
    }
    auto [x1, x2, y1, y2] = get_bounds();
    for (auto x : {x1, x2}) for (auto y : {y1, y2}) {
        solutions.push_back({x, y});
        vector<int> add;
        for (int i = 0; i < N; i++) if (!covered[i]) {
            auto [l, d, r, u] = rect[i];
            if (l <= x && x <= r && d <= y && y <= u) add.push_back(i);
        }
        for (int i : add) covered[i] = 1;
        rec(k - 1);
        for (int i : add) covered[i] = 0;
        solutions.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    rect.resize(N);
    for (auto &[l, d, r, u] : rect) cin >> l >> d >> r >> u;
    covered.resize(N);
    rec(K);
    auto [x1, x2, y1, y2] = get_bounds();
    vector<pi> edges;
    int n = 0;
    vector<ar<int, 3>> A, B, C, D;
    vector<int> must;
    for (int i = 0; i < N; i++) {
        auto [l, d, r, u] = rect[i];
        if (l <= x1 && x1 <= r && d <= y1 && y2 <= u) continue;
        if (l <= x2 && x2 <= r && d <= y1 && y2 <= u) continue;
        if (l <= x1 && x2 <= r && d <= y1 && y1 <= u) continue;
        if (l <= x1 && x2 <= r && d <= y2 && y2 <= u) continue;
        int cnt = 0;
        int bm = 0;
        if (d <= y1 && y1 <= u) {
            assert(max(x1, l) <= min(x2, r));
            A.push_back({max(x1, l), min(x2, r), i * 2 + cnt});
            cnt++;
            bm |= 1;
        }
        if (d <= y2 && y2 <= u) {
            assert(max(x1, l) <= min(x2, r));
            B.push_back({max(x1, l), min(x2, r), i * 2 + cnt});
            cnt++;
            bm |= 2;
        }
        if (l <= x1 && x1 <= r) {
            assert(max(y1, d) <= min(y2, u));
            C.push_back({max(y1, d), min(y2, u), i * 2 + cnt});
            cnt++;
            bm |= 4;
        }
        if (l <= x2 && x2 <= r) {
            assert(max(y1, d) <= min(y2, u));
            D.push_back({max(y1, d), min(y2, u), i * 2 + cnt});
            cnt++;
            bm |= 8;
        }
        // bug(bm);
        if (cnt == 1) {
            bug(i);
            must.push_back(i * 2);
            edges.push_back({i * 2 + 1, i * 2});
        } else assert(cnt == 2);
    }
    vector<pi> ban;
    auto process = [&](const vector<ar<int, 3>> v) {
        auto one = v, two = v;
        sort(all(one), [&](auto x, auto y) {
            return x[1] < y[1];
        });
        sort(all(two), [&](auto x, auto y) {
            return x[0] > y[0];
        });
        vi f(sz(v)), g(sz(v));
        for (int i = 0; i < sz(v); i++) {
            if (i == 0) {
                f[i] = one[i][2] ^ 1;
                g[i] = two[i][2] ^ 1;
            } else {
                f[i] = N * 2 + (n++);
                g[i] = N * 2 + (n++);
                edges.push_back({f[i], one[i][2] ^ 1});
                edges.push_back({f[i], f[i - 1]});
                edges.push_back({g[i], two[i][2] ^ 1});
                edges.push_back({g[i], g[i - 1]});
            }
        }
        for (auto [l, r, i] : v) {
            if (one[0][1] < l) {
                int low = 0, hi = sz(one) - 1;
                while (low < hi) {
                    int m = (low + hi) / 2 + 1;
                    one[m][1] < l ? low = m : hi = m - 1;
                }
                edges.push_back({i, f[low]});
            }
            if (two[0][0] > r) {
                int low = 0, hi = sz(two) - 1;
                while (low < hi) {
                    int m = (low + hi) / 2 + 1;
                    two[m][0] > r ? low = m : hi = m - 1;
                }
                edges.push_back({i, g[low]});
            }
        }
    };
    process(A);
    process(B);
    process(C);
    process(D);
    SCC S(N * 2 + n);
    for (auto [i, j] : edges) S.make_edge(i, j);
    S.solve();
    for (int i = 0; i < N; i++) {
        if (S.id[i * 2] == S.id[i * 2 + 1])
            bug(i, S.id[i * 2], S.id[i * 2 + 1]);
        assert(S.id[i * 2] != S.id[i * 2 + 1]);
    }
    auto go = [&](const vector<ar<int, 3>> v, int x1, int x2) {
        for (auto [l, r, i] : v) if (S.id[i] > S.id[i ^ 1]) x1 = max(x1, l), x2 = min(x2, r);
        bug(x1, x2);
        assert(x1 <= x2);
        return x1;
    };
    solutions.push_back({go(A, x1, x2), y1});
    solutions.push_back({go(B, x1, x2), y2});
    solutions.push_back({x1, go(C, y1, y2)});
    solutions.push_back({x2, go(D, y1, y2)});
    pr();
}

• 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