oj.uz

Submission #251341

# Submission time Handle Problem Language Result Execution time Memory
251341 2020-07-20T22:00:05 Z imeimi2000 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 208 ms 19908 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define x1 x.x
#define y1 x.y
#define x2 y.x
#define y2 y.y

using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppp;

const int inf = 1e9 + 5;

void flip_x(ppp &i) {
    swap(i.x1, i.x2);
    i.x1 = inf - i.x1;
    i.x2 = inf - i.x2;
}

void flip_y(ppp &i) {
    swap(i.y1, i.y2);
    i.y1 = inf - i.y1;
    i.y2 = inf - i.y2;
}

struct get_min {
    vector<pii> V;
    void add(int p, int x) {
        V.emplace_back(p, x);
    }
    void init() {
        V.emplace_back(-5, inf);
        sort(V.begin(), V.end());
        int mn = inf;
        for (pii &i : V) {
            mn = min(mn, i.y);
            i.y = mn;
        }
    }
    int find(int x) const {
        return (lower_bound(V.begin(), V.end(), pii(x, -inf)) - 1)->y;
    }
};

vector<pii> solve4(vector<ppp> R, int l, int d, int r, int u) {
    // l > r and u > d
    int l1 = d, l2 = u;
    int d1 = l, d2 = r;
    int r1 = d, r2 = u;
    int u1 = l, u2 = r;
    get_min ld, dr, ru, ul, rl, du;
    vector<int> cp;
    for (ppp &i : R) {
        i.x1 = max(i.x1, l);
        i.y1 = max(i.y1, d);
        i.x2 = min(i.x2, r);
        i.y2 = min(i.y2, u);
        int in_l = i.x1 == l, in_d = d == i.y1;
        int in_r = i.x2 == r, in_u = u == i.y2;
        int cnt = in_l + in_d + in_r + in_u;
        if (in_l) cp.push_back(i.y1), cp.push_back(i.y2);
        if (cnt > 2) continue;
        if (cnt == 1) {
            if (in_l) {
                l1 = max(l1, i.y1);
                l2 = min(l2, i.y2);
            }
            if (in_d) {
                d1 = max(d1, i.x1);
                d2 = min(d2, i.x2);
            }
            if (in_r) {
                r1 = max(r1, i.y1);
                r2 = min(r2, i.y2);
            }
            if (in_u) {
                u1 = max(u1, i.x1);
                u2 = min(u2, i.x2);
            }
            continue;
        }
        if (in_l && in_r) {
            l1 = max(l1, i.y1);
            r2 = min(r2, i.y2);
            rl.add(i.y2, -i.y1);
            continue;
        }
        if (in_d && in_u) {
            u1 = max(u1, i.x1);
            d2 = min(d2, i.x2);
            du.add(i.x2, -i.x1);
            continue;
        }
        if (in_l && in_d) ld.add(i.y2 - d, i.x2 - l);
        if (in_d && in_r) dr.add(r - i.x1, i.y2 - d);
        if (in_r && in_u) ru.add(u - i.y1, r - i.x1);
        if (in_u && in_l) ul.add(i.x2 - l, u - i.y1);
    }
    ld.init();
    dr.init();
    ru.init();
    ul.init();
    sort(cp.rbegin(), cp.rend());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    vector<pii> ret;
    for (int ly : cp) {
        if (ly < l1 || l2 < ly) continue;
        int dx = min(d2, l + ld.find(ly - d));
        if (dx < d1) continue;
        int ry = min(r2, d + dr.find(r - dx));
        if (ry < r1) continue;
        if (ly > ry && ry < -rl.find(ly)) continue;
        int ux = max(u1, r - ru.find(u - ry));
        if (u2 < ux) continue;
        if (dx < ux && dx < -du.find(ux)) continue;
        if (u - ul.find(ux - l) < ly) continue;
        ret.emplace_back(l, ly);
        ret.emplace_back(dx, d);
        ret.emplace_back(r, ry);
        ret.emplace_back(ux, u);
        break;
    }
    return ret;
}

vector<pii> solve(vector<ppp> R, int k) {
    if (R.empty()) return vector<pii>(k, pii(1, 1));
    int l = inf, d = inf, r = 0, u = 0;
    for (ppp i : R) {
        l = min(l, i.x2);
        d = min(d, i.y2);
        r = max(r, i.x1);
        u = max(u, i.y1);
    }
    if (k == 1) {
        vector<pii> ret;
        if (r <= l && u <= d) ret.emplace_back(l, d);
        return ret;
    }
    for (int x : { l, r }) for (int y : { d, u }) {
        vector<ppp> nxt;
        for (ppp i : R) {
            if (i.x1 <= x && x <= i.x2 && i.y1 <= y && y <= i.y2) continue;
            nxt.push_back(i);
        }
        vector<pii> ret = solve(nxt, k - 1);
        if (ret.empty()) continue;
        ret.emplace_back(x, y);
        return ret;
    }
    if (k <= 3) return vector<pii>();
    assert(l < r && d < u);
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            vector<pii> ans = solve4(R, l, d, r, u);
            if (!ans.empty()) {
                for (pii &p : ans) {
                    if (i) p.x = inf - p.x;
                    if (j) p.y = inf - p.y;
                }
                return ans;
            }
            for (ppp &i : R) flip_y(i);
            swap(d, u);
            d = inf - d;
            u = inf - u;
        }
        for (ppp &i : R) flip_x(i);
        swap(l, r);
        l = inf - l;
        r = inf - r;
    }
    return vector<pii>();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<ppp> R(n);
    for (int i = 0; i < n; ++i) {
        cin >> R[i].x1 >> R[i].y1 >> R[i].x2 >> R[i].y2;
    }
    vector<pii> ans = solve(R, k);
    if (ans.empty()) return 1;
    for (pii i : ans) printf("%d %d\n", i.x, i.y);
    return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 4 ms 600 KB Output is correct
14 Runtime error 4 ms 596 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 360 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 102 ms 6604 KB Output is correct
6 Correct 98 ms 6608 KB Output is correct
7 Correct 116 ms 6600 KB Output is correct
8 Correct 91 ms 6648 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 96 ms 9144 KB Output is correct
6 Correct 98 ms 8868 KB Output is correct
7 Correct 101 ms 9068 KB Output is correct
8 Correct 104 ms 11624 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 484 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 101 ms 10044 KB Output is correct
14 Correct 98 ms 10220 KB Output is correct
15 Correct 100 ms 8900 KB Output is correct
16 Correct 98 ms 9072 KB Output is correct
17 Correct 101 ms 11500 KB Output is correct
18 Correct 119 ms 8944 KB Output is correct
19 Correct 109 ms 11920 KB Output is correct
20 Correct 111 ms 13164 KB Output is correct
21 Correct 208 ms 19908 KB Output is correct
22 Correct 121 ms 13620 KB Output is correct
23 Correct 137 ms 17340 KB Output is correct
24 Correct 134 ms 18536 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 4 ms 600 KB Output is correct
14 Runtime error 4 ms 596 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -