oj.uz

Submission #898705

# Submission time Handle Problem Language Result Execution time Memory
898705 2024-01-05T03:38:17 Z box Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 179 ms 4988 KB 
#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, comps;
    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);
    }
    bool dfs2(int i, int c) {
        id[i] = c;
        bool f = i < N * 2;
        for (int j : rg[i]) if (id[j] == -1) f |= dfs2(j, c);
        return f;
    }
    void solve() {
        for (int i = 0; i < sz(id); i++) if (!id[i]) dfs1(i);
        reverse(all(order)), fill(all(id), -1);
        for (int i : order) if (id[i] == -1) {
            if (dfs2(i, i)) comps.push_back(i);
        }
        reverse(all(comps));
    }
};

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) {
        // for (auto x : v) for (auto y : v)
        //     if (max(x[0], y[0]) > min(x[1], y[1])) {
        //         ban.push_back({x[2], y[2]});
        //         edges.push_back({x[2], y[2] ^ 1});
        //         edges.push_back({y[2], x[2] ^ 1});
        //     }
        // return;
        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]);
    }
    vi what(N * 2 + n, -1);
    for (int i : S.comps) if (what[i] == -1) {
        what[i] = 1;
        what[S.id[i ^ 1]] = 0;
    }
    for (int i : must) {
        assert(what[S.id[i]]);
        assert(!what[S.id[i ^ 1]]);
    }
    for (auto [i, j] : ban) assert(!what[S.id[i]] || !what[S.id[j]]);
    auto go = [&](const vector<ar<int, 3>> v, int x1, int x2) {
        for (auto [l, r, i] : v) if (what.at(S.id[i])) 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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 2 ms 348 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 6 ms 348 KB Output is correct
14 Runtime error 9 ms 2388 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 62 ms 4740 KB Output is correct
6 Correct 59 ms 4724 KB Output is correct
7 Correct 60 ms 4724 KB Output is correct
8 Correct 63 ms 4564 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 63 ms 4820 KB Output is correct
6 Correct 73 ms 4916 KB Output is correct
7 Correct 62 ms 4820 KB Output is correct
8 Correct 71 ms 4660 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 64 ms 4560 KB Output is correct
14 Correct 64 ms 4488 KB Output is correct
15 Correct 62 ms 4560 KB Output is correct
16 Correct 70 ms 4820 KB Output is correct
17 Correct 66 ms 4748 KB Output is correct
18 Correct 63 ms 4560 KB Output is correct
19 Correct 69 ms 4988 KB Output is correct
20 Correct 78 ms 4472 KB Output is correct
21 Correct 179 ms 4860 KB Output is correct
22 Correct 138 ms 4780 KB Output is correct
23 Correct 102 ms 4760 KB Output is correct
24 Correct 109 ms 4776 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 6 ms 348 KB Output is correct
14 Runtime error 9 ms 2388 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -