oj.uz

Submission #384658

# Submission time Handle Problem Language Result Execution time Memory
384658 2021-04-02T03:09:59 Z timmyfeng Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 331 ms 155532 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3200000, 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 114 ms 150764 KB Output is correct
2 Correct 104 ms 150764 KB Output is correct
3 Correct 104 ms 150764 KB Output is correct
4 Correct 106 ms 150764 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 150732 KB Output is correct
2 Correct 106 ms 150660 KB Output is correct
3 Correct 103 ms 150764 KB Output is correct
4 Correct 104 ms 150784 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 150764 KB Output is correct
2 Correct 104 ms 150764 KB Output is correct
3 Correct 105 ms 150764 KB Output is correct
4 Correct 104 ms 150764 KB Output is correct
5 Correct 108 ms 150696 KB Output is correct
6 Correct 105 ms 150764 KB Output is correct
7 Correct 103 ms 150764 KB Output is correct
8 Correct 102 ms 150764 KB Output is correct
9 Correct 105 ms 150764 KB Output is correct
10 Correct 104 ms 150764 KB Output is correct
11 Correct 104 ms 150764 KB Output is correct
12 Correct 105 ms 150764 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 150764 KB Output is correct
2 Correct 104 ms 150764 KB Output is correct
3 Correct 114 ms 150764 KB Output is correct
4 Correct 104 ms 150764 KB Output is correct
5 Correct 106 ms 150764 KB Output is correct
6 Correct 120 ms 150636 KB Output is correct
7 Correct 105 ms 150764 KB Output is correct
8 Correct 105 ms 150764 KB Output is correct
9 Correct 104 ms 150764 KB Output is correct
10 Correct 104 ms 150764 KB Output is correct
11 Correct 109 ms 150784 KB Output is correct
12 Correct 105 ms 150764 KB Output is correct
13 Correct 109 ms 150764 KB Output is correct
14 Incorrect 115 ms 151532 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 114 ms 150764 KB Output is correct
2 Correct 104 ms 150764 KB Output is correct
3 Correct 104 ms 150764 KB Output is correct
4 Correct 106 ms 150764 KB Output is correct
5 Correct 199 ms 155116 KB Output is correct
6 Correct 197 ms 155116 KB Output is correct
7 Correct 198 ms 155156 KB Output is correct
8 Correct 197 ms 155116 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 150732 KB Output is correct
2 Correct 106 ms 150660 KB Output is correct
3 Correct 103 ms 150764 KB Output is correct
4 Correct 104 ms 150784 KB Output is correct
5 Correct 205 ms 155320 KB Output is correct
6 Correct 216 ms 155532 KB Output is correct
7 Correct 206 ms 155500 KB Output is correct
8 Correct 225 ms 155340 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 150764 KB Output is correct
2 Correct 104 ms 150764 KB Output is correct
3 Correct 105 ms 150764 KB Output is correct
4 Correct 104 ms 150764 KB Output is correct
5 Correct 108 ms 150696 KB Output is correct
6 Correct 105 ms 150764 KB Output is correct
7 Correct 103 ms 150764 KB Output is correct
8 Correct 102 ms 150764 KB Output is correct
9 Correct 105 ms 150764 KB Output is correct
10 Correct 104 ms 150764 KB Output is correct
11 Correct 104 ms 150764 KB Output is correct
12 Correct 105 ms 150764 KB Output is correct
13 Correct 212 ms 155244 KB Output is correct
14 Correct 204 ms 154988 KB Output is correct
15 Correct 242 ms 155244 KB Output is correct
16 Correct 226 ms 155084 KB Output is correct
17 Correct 203 ms 155116 KB Output is correct
18 Correct 208 ms 155244 KB Output is correct
19 Correct 206 ms 155116 KB Output is correct
20 Correct 215 ms 155048 KB Output is correct
21 Correct 331 ms 155320 KB Output is correct
22 Correct 273 ms 155168 KB Output is correct
23 Correct 248 ms 155188 KB Output is correct
24 Correct 259 ms 155196 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 150764 KB Output is correct
2 Correct 104 ms 150764 KB Output is correct
3 Correct 114 ms 150764 KB Output is correct
4 Correct 104 ms 150764 KB Output is correct
5 Correct 106 ms 150764 KB Output is correct
6 Correct 120 ms 150636 KB Output is correct
7 Correct 105 ms 150764 KB Output is correct
8 Correct 105 ms 150764 KB Output is correct
9 Correct 104 ms 150764 KB Output is correct
10 Correct 104 ms 150764 KB Output is correct
11 Correct 109 ms 150784 KB Output is correct
12 Correct 105 ms 150764 KB Output is correct
13 Correct 109 ms 150764 KB Output is correct
14 Incorrect 115 ms 151532 KB Output isn't correct
15 Halted 0 ms 0 KB -