oj.uz

Submission #998080

# Submission time Handle Problem Language Result Execution time Memory
998080 2024-06-13T09:25:01 Z arbuzick Izvanzemaljci (COI21_izvanzemaljci) C++17
26 / 100
 3000 ms 8264 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

constexpr long long inf = (long long)1e18 + 7;

constexpr long long vl = 3000000001;

struct Point {
    int x, y;

    Point(int _x = 0, int _y = 0) {
        x = _x, y = _y;
    }
};

struct Answer {
    vector<pair<Point, int>> squares;
    int mx;

    Answer() {
        mx = 0;
    }

    void add(Point p, int side) {
        squares.emplace_back(p, side);
        mx = max(mx, side);
    }

    bool operator<(Answer b) {
        return mx < b.mx;
    }
};

Answer split2(vector<Point> a, long long mn_x, long long mx_x, long long mn_y, long long mx_y) {
    auto check = [&](Answer ans) -> bool {
        for (int i = 0; i < (int)ans.squares.size(); ++i) {
            if (ans.squares[i].first.x <= mn_x || ans.squares[i].first.x + ans.squares[i].second >= mx_x) {
                return false;
            }
            if (ans.squares[i].first.y < mn_y || ans.squares[i].first.y + ans.squares[i].second >= mx_y) {
                return false;
            }
        }
        return true;
    };
    int n = a.size();
    sort(a.begin(), a.end(), [&](Point a, Point b) -> bool {
        return a.x < b.x;
    });
    vector<int> pr_mn(n + 1, inf), pr_mx(n + 1, -inf), suf_mn(n + 1, inf), suf_mx(n + 1, -inf);
    for (int i = 0; i < n; ++i) {
        pr_mn[i + 1] = min(pr_mn[i], a[i].y);
        pr_mx[i + 1] = max(pr_mx[i], a[i].y);
    }
    for (int i = n - 1; i >= 0; --i) {
        suf_mn[i] = min(suf_mn[i + 1], a[i].y);
        suf_mx[i] = max(suf_mx[i + 1], a[i].y);
    }
    Answer ans;
    ans.add(Point(0, 0), inf);
    for (int i = 0; i + 1 < n; ++i) {
        if (a[i].x == a[i + 1].x) {
            continue;
        }
        Answer ans_nw;
        int side1 = max(1LL, max(a[i].x - a[0].x, pr_mx[i + 1] - pr_mn[i + 1]));
        Point p1(a[i].x - side1, pr_mn[i + 1]);
        if (p1.x <= mn_x) {
            p1.x = a[i + 1].x - 1 - side1;
            if (p1.x <= mn_x) {
                continue;
            }
        }
        if (p1.y + side1 >= mx_y) {
            p1.y = pr_mx[i + 1] - side1;
        }
        ans_nw.add(p1, side1);
        int side2 = max(1LL, max(a[n - 1].x - a[i + 1].x, suf_mx[i + 1] - suf_mn[i + 1]));
        Point p2(a[i + 1].x, suf_mn[i + 1]);
        if (p2.x + side2 >= mx_x) {
            p2.x = max(a[i].x + 1, a[n - 1].x - side2);
            if (p2.x + side2 >= mx_x) {
                continue;
            }
        }
        if (p2.y + side2 >= mx_y) {
            p2.y = suf_mx[i + 1] - side2;
        }
        ans_nw.add(p2, side2);
        if (check(ans_nw) && ans_nw < ans) {
            ans = ans_nw;
        }
    }
    int side = max(1LL, max(a[n - 1].x - a[0].x, pr_mx[n] - pr_mn[n]));
    Point p(a[0].x, pr_mn[n]);
    if (p.x + side >= mx_x) {
        p.x = a[n - 1].x - side;
    }
    if (p.y + side >= mx_y) {
        p.y = pr_mx[n] - side;
    }
    Answer ans_nw;
    ans_nw.add(p, side);
    if (p.x - 2 >= mn_x && p.y - 2 >= mn_y) {
        ans_nw.add(Point(p.x - 2, p.y - 2), 1);
        if (check(ans_nw) && ans_nw < ans) {
            ans = ans_nw;
        }
    } else if (p.x - 2 >= mn_x && p.y + side + 2 <= mx_y) {
        ans_nw.add(Point(p.x - 2, p.y + side + 1), 1);
        if (check(ans_nw) && ans_nw < ans) {
            ans = ans_nw;
        }
    } else if (p.x + side + 2 <= mx_x && p.y - 2 >= mn_y) {
        ans_nw.add(Point(p.x + side + 1, p.y - 2), 1);
        if (check(ans_nw) && ans_nw < ans) {
            ans = ans_nw;
        }
    } else if (p.x + side + 2 <= mx_x && p.y + side + 2 <= mx_y) {
        ans_nw.add(Point(p.x + side + 1, p.y + side + 1), 1);
        if (check(ans_nw) && ans_nw < ans) {
            ans = ans_nw;
        }
    } else {
        exit(1);
    }
    return ans;
}

Answer get_ans(int n, vector<Point> a) {
    auto check = [&](Answer ans) -> bool {
        for (int i = 0; i < 3; ++i) {
            if (ans.squares[i].first.x < -vl || ans.squares[i].first.x > vl) {
                return false;
            }
            if (ans.squares[i].first.y < -vl || ans.squares[i].first.y > vl) {
                return false;
            }
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = i + 1; j < 3; ++j) {
                if (min(ans.squares[i].first.x + ans.squares[i].second, ans.squares[j].first.x + ans.squares[j].second) >= max(ans.squares[i].first.x, ans.squares[j].first.x) &&
                    min(ans.squares[i].first.y + ans.squares[i].second, ans.squares[j].first.y + ans.squares[j].second) >= max(ans.squares[i].first.y, ans.squares[j].first.y)) {
                    return false;
                }
            }
        }
        return true;
    };

    sort(a.begin(), a.end(), [&](Point a, Point b) -> bool {
        return a.x < b.x;
    });
    Answer ans;
    ans.add(Point(0, 0), inf);
    int mn_y = inf, mx_y = -inf;
    for (int i = 0; i < n; ++i) {
        mn_y = min(mn_y, a[i].y);
        mx_y = max(mx_y, a[i].y);
        if (i == n - 1 || a[i].x == a[i + 1].x) {
            continue;
        }
        vector<Point> b;
        for (int j = i + 1; j < n; ++j) {
            b.push_back(a[j]);
        }
        Answer ans1_ans = split2(b, a[i].x, vl, -vl, vl);
        for (int j = 0; j < (int)b.size(); ++j) {
            swap(b[j].x, b[j].y);
        }
        Answer ans2_ans = split2(b, -vl, vl, a[i].x, vl);
        for (int i = 0; i < 2; ++i) {
            swap(ans2_ans.squares[i].first.x, ans2_ans.squares[i].first.y);
        }
        if (ans2_ans < ans1_ans) {
            ans1_ans = ans2_ans;
        }
        int side = max(1LL, max(a[i].x - a[0].x, mx_y - mn_y));
        ans1_ans.add(Point(a[i].x - side, mn_y), side);
        if (ans1_ans < ans) {
            ans = ans1_ans;
        }
    }
    int side = max(1LL, max(a[n - 1].x - a[0].x, mx_y - mn_y));
    Point p(a[0].x, mn_y);
    Answer ans_nw;
    ans_nw.add(p, side);
    if (p.x - 4 >= -vl && p.y - 4 >= -vl) {
        ans_nw.add(Point(p.x - 2, p.y - 2), 1);
        ans_nw.add(Point(p.x - 4, p.y - 4), 1);
        if (ans_nw < ans) {
            ans = ans_nw;
        }
    } else if (p.x - 4 >= -vl && p.y + 4 <= vl) {
        ans_nw.add(Point(p.x - 2, p.y + 1), 1);
        ans_nw.add(Point(p.x - 4, p.y + 3), 1);
        if (ans_nw < ans) {
            ans = ans_nw;
        }
    } else if (p.x + 4 <= vl && p.y - 4 >= vl) {
        ans_nw.add(Point(p.x + 1, p.y - 2), 1);
        ans_nw.add(Point(p.x + 3, p.y - 4), 1);
        if (ans_nw < ans) {
            ans = ans_nw;
        }
    } else if (p.x + 4 <= vl && p.y + 4 <= vl) {
        ans_nw.add(Point(p.x + 1, p.y + 1), 1);
        ans_nw.add(Point(p.x + 3, p.y + 3), 1);
        if (ans_nw < ans) {
            ans = ans_nw;
        }
    }

    mn_y = inf, mx_y = -inf;
    for (int i = n - 1; i > 0; --i) {
        mn_y = min(mn_y, a[i].y);
        mx_y = max(mx_y, a[i].y);
        if (i == 0 || a[i].x == a[i - 1].x) {
            continue;
        }
        vector<Point> b;
        for (int j = 0; j < i; ++j) {
            b.push_back(a[j]);
        }
        Answer ans1_ans = split2(b, -vl, a[i].x, -vl, vl);
        for (int j = 0; j < (int)b.size(); ++j) {
            swap(b[j].x, b[j].y);
        }
        Answer ans2_ans = split2(b, -vl, vl, -vl, a[i].x);
        for (int i = 0; i < 2; ++i) {
            swap(ans2_ans.squares[i].first.x, ans2_ans.squares[i].first.y);
        }
        if (ans2_ans < ans1_ans) {
            ans1_ans = ans2_ans;
        }
        int side = max(1LL, max(a[n - 1].x - a[i].x, mx_y - mn_y));
        ans1_ans.add(Point(a[i].x, mn_y), side);
        if (ans1_ans < ans) {
            ans = ans1_ans;
        }
    }

    assert(check(ans));

    return ans;
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<Point> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].x >> a[i].y;
    }
    if (k == 1) {
        int mn_x = inf, mx_x = -inf, mn_y = inf, mx_y = -inf;
        for (int i = 0; i < n; ++i) {
            mn_x = min(mn_x, a[i].x);
            mx_x = max(mx_x, a[i].x);
            mn_y = min(mn_y, a[i].y);
            mx_y = max(mx_y, a[i].y);
        }
        cout << mn_x << ' ' << mn_y << ' ' << max(1LL, max(mx_x - mn_x, mx_y - mn_y)) << '\n';
    } else if (k == 2) {
        auto ans1 = split2(a, -vl, vl, -vl, vl);
        for (int i = 0; i < n; ++i) {
            swap(a[i].x, a[i].y);
        }
        auto ans2 = split2(a, -vl, vl, -vl, vl);
        for (int i = 0; i < k; ++i) {
            swap(ans2.squares[i].first.x, ans2.squares[i].first.y);
        }
        if (ans1 < ans2) {
            for (int i = 0; i < k; ++i) {
                cout << ans1.squares[i].first.x << ' ' << ans1.squares[i].first.y << ' ' << ans1.squares[i].second << '\n';
            }
        } else {
            for (int i = 0; i < k; ++i) {
                cout << ans2.squares[i].first.x << ' ' << ans2.squares[i].first.y << ' ' << ans2.squares[i].second << '\n';
            }
        }
    } else if (k == 3) {
        auto ans1 = get_ans(n, a);
        for (int i = 0; i < n; ++i) {
            swap(a[i].x, a[i].y);
        }
        auto ans2 = get_ans(n, a);
        for (int i = 0; i < k; ++i) {
            swap(ans2.squares[i].first.x, ans2.squares[i].first.y);
        }
        auto check = [&](Answer ans) -> bool {
            for (int i = 0; i < k; ++i) {
                if (ans.squares[i].first.x < -vl || ans.squares[i].first.x > vl) {
                    return false;
                }
                if (ans.squares[i].first.y < -vl || ans.squares[i].first.y > vl) {
                    return false;
                }
            }
            for (int i = 0; i < k; ++i) {
                for (int j = i + 1; j < k; ++j) {
                    if (min(ans.squares[i].first.x + ans.squares[i].second, ans.squares[j].first.x + ans.squares[j].second) >= max(ans.squares[i].first.x, ans.squares[j].first.x) &&
                        min(ans.squares[i].first.y + ans.squares[i].second, ans.squares[j].first.y + ans.squares[j].second) >= max(ans.squares[i].first.y, ans.squares[j].first.y)) {
                        return false;
                    }
                }
            }
            return true;
        };
        assert(check(ans1));
        assert(check(ans2));
        if (ans1 < ans2) {
            for (int i = 0; i < k; ++i) {
                cout << ans1.squares[i].first.x << ' ' << ans1.squares[i].first.y << ' ' << ans1.squares[i].second << '\n';
            }
        } else {
            for (int i = 0; i < k; ++i) {
                cout << ans2.squares[i].first.x << ' ' << ans2.squares[i].first.y << ' ' << ans2.squares[i].second << '\n';
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 46 ms 6664 KB Output is correct
11 Correct 45 ms 6640 KB Output is correct
12 Correct 47 ms 6644 KB Output is correct
13 Correct 44 ms 6648 KB Output is correct
14 Correct 44 ms 6744 KB Output is correct
15 Correct 45 ms 6644 KB Output is correct
16 Correct 44 ms 6648 KB Output is correct
17 Correct 39 ms 6028 KB Output is correct
18 Correct 38 ms 5980 KB Output is correct
19 Correct 37 ms 5468 KB Output is correct
20 Correct 38 ms 5756 KB Output is correct
21 Correct 43 ms 6668 KB Output is correct
22 Correct 44 ms 6676 KB Output is correct
23 Correct 45 ms 6652 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 672 KB Output is correct
2 Correct 266 ms 668 KB Output is correct
3 Correct 273 ms 596 KB Output is correct
4 Correct 272 ms 596 KB Output is correct
5 Correct 268 ms 552 KB Output is correct
6 Correct 267 ms 592 KB Output is correct
7 Correct 266 ms 540 KB Output is correct
8 Correct 274 ms 804 KB Output is correct
9 Correct 265 ms 592 KB Output is correct
10 Correct 265 ms 592 KB Output is correct
11 Correct 279 ms 592 KB Output is correct
12 Correct 297 ms 592 KB Output is correct
13 Correct 215 ms 592 KB Output is correct
14 Correct 219 ms 592 KB Output is correct
15 Correct 221 ms 592 KB Output is correct
16 Correct 215 ms 592 KB Output is correct
17 Correct 212 ms 796 KB Output is correct
18 Correct 226 ms 524 KB Output is correct
19 Correct 201 ms 592 KB Output is correct
20 Correct 212 ms 596 KB Output is correct
21 Incorrect 252 ms 656 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 600 KB Output is correct
2 Correct 268 ms 596 KB Output is correct
3 Correct 265 ms 596 KB Output is correct
4 Correct 265 ms 552 KB Output is correct
5 Correct 271 ms 548 KB Output is correct
6 Correct 266 ms 592 KB Output is correct
7 Correct 270 ms 540 KB Output is correct
8 Correct 270 ms 596 KB Output is correct
9 Correct 265 ms 592 KB Output is correct
10 Correct 269 ms 596 KB Output is correct
11 Correct 313 ms 592 KB Output is correct
12 Correct 269 ms 852 KB Output is correct
13 Correct 272 ms 596 KB Output is correct
14 Execution timed out 3045 ms 8264 KB Time limit exceeded
15 Halted 0 ms 0 KB -