oj.uz

Submission #384657

# Submission time Handle Problem Language Result Execution time Memory
384657 2021-04-02T03:04:25 Z timmyfeng Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 233 ms 15180 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9836 KB Output is correct
2 Correct 9 ms 9812 KB Output is correct
3 Correct 8 ms 9856 KB Output is correct
4 Correct 8 ms 9836 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9836 KB Output is correct
2 Correct 9 ms 9836 KB Output is correct
3 Correct 9 ms 9964 KB Output is correct
4 Correct 9 ms 9836 KB Output is correct

Subtask #3
3.0 / 3.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9836 KB Output is correct
2 Correct 9 ms 9836 KB Output is correct
3 Correct 9 ms 9836 KB Output is correct
4 Correct 9 ms 9836 KB Output is correct
5 Correct 9 ms 9836 KB Output is correct
6 Correct 9 ms 9836 KB Output is correct
7 Correct 9 ms 9836 KB Output is correct
8 Correct 8 ms 9836 KB Output is correct
9 Correct 11 ms 9836 KB Output is correct
10 Correct 9 ms 9836 KB Output is correct
11 Correct 9 ms 9836 KB Output is correct
12 Correct 8 ms 9836 KB Output is correct
13 Correct 13 ms 9836 KB Output is correct
14 Incorrect 18 ms 10604 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9836 KB Output is correct
2 Correct 9 ms 9812 KB Output is correct
3 Correct 8 ms 9856 KB Output is correct
4 Correct 8 ms 9836 KB Output is correct
5 Correct 103 ms 14700 KB Output is correct
6 Correct 105 ms 14700 KB Output is correct
7 Correct 103 ms 14700 KB Output is correct
8 Correct 103 ms 14700 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9836 KB Output is correct
2 Correct 9 ms 9836 KB Output is correct
3 Correct 9 ms 9964 KB Output is correct
4 Correct 9 ms 9836 KB Output is correct
5 Correct 107 ms 14828 KB Output is correct
6 Correct 114 ms 15180 KB Output is correct
7 Correct 107 ms 14828 KB Output is correct
8 Correct 119 ms 14980 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9836 KB Output is correct
2 Correct 9 ms 9836 KB Output is correct
3 Correct 9 ms 9836 KB Output is correct
4 Correct 8 ms 9836 KB Output is correct
5 Correct 8 ms 9836 KB Output is correct
6 Correct 8 ms 9836 KB Output is correct
7 Correct 9 ms 9836 KB Output is correct
8 Correct 9 ms 9836 KB Output is correct
9 Correct 10 ms 9836 KB Output is correct
10 Correct 10 ms 9836 KB Output is correct
11 Correct 9 ms 9836 KB Output is correct
12 Correct 9 ms 9836 KB Output is correct
13 Correct 108 ms 14728 KB Output is correct
14 Correct 108 ms 14572 KB Output is correct
15 Correct 109 ms 14828 KB Output is correct
16 Correct 111 ms 14828 KB Output is correct
17 Correct 108 ms 14700 KB Output is correct
18 Correct 106 ms 14700 KB Output is correct
19 Correct 110 ms 14828 KB Output is correct
20 Correct 118 ms 14700 KB Output is correct
21 Correct 233 ms 15092 KB Output is correct
22 Correct 176 ms 14748 KB Output is correct
23 Correct 150 ms 14772 KB Output is correct
24 Correct 160 ms 14588 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9836 KB Output is correct
2 Correct 9 ms 9836 KB Output is correct
3 Correct 9 ms 9836 KB Output is correct
4 Correct 9 ms 9836 KB Output is correct
5 Correct 9 ms 9836 KB Output is correct
6 Correct 9 ms 9836 KB Output is correct
7 Correct 9 ms 9836 KB Output is correct
8 Correct 8 ms 9836 KB Output is correct
9 Correct 11 ms 9836 KB Output is correct
10 Correct 9 ms 9836 KB Output is correct
11 Correct 9 ms 9836 KB Output is correct
12 Correct 8 ms 9836 KB Output is correct
13 Correct 13 ms 9836 KB Output is correct
14 Incorrect 18 ms 10604 KB Output isn't correct
15 Halted 0 ms 0 KB -