oj.uz

Submission #998084

# Submission time Handle Problem Language Result Execution time Memory
998084 2024-06-13T09:29:17 Z arbuzick Izvanzemaljci (COI21_izvanzemaljci) C++17
26 / 100
 3000 ms 8272 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 = max(a[0].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;
        }
    } else {
        exit(1);
    }

    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 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 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 18 ms 1884 KB Output is correct
8 Correct 15 ms 1884 KB Output is correct
9 Correct 16 ms 1880 KB Output is correct
10 Correct 15 ms 1880 KB Output is correct
11 Correct 14 ms 1880 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 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 45 ms 6676 KB Output is correct
11 Correct 44 ms 6660 KB Output is correct
12 Correct 45 ms 6648 KB Output is correct
13 Correct 43 ms 6648 KB Output is correct
14 Correct 44 ms 6648 KB Output is correct
15 Correct 43 ms 6648 KB Output is correct
16 Correct 43 ms 6656 KB Output is correct
17 Correct 40 ms 6028 KB Output is correct
18 Correct 37 ms 5980 KB Output is correct
19 Correct 35 ms 5368 KB Output is correct
20 Correct 46 ms 5756 KB Output is correct
21 Correct 43 ms 6656 KB Output is correct
22 Correct 44 ms 6648 KB Output is correct
23 Correct 47 ms 6644 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 372 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 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 360 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Incorrect 0 ms 344 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 536 KB Output is correct
2 Correct 330 ms 532 KB Output is correct
3 Correct 329 ms 596 KB Output is correct
4 Correct 346 ms 552 KB Output is correct
5 Correct 331 ms 548 KB Output is correct
6 Correct 328 ms 596 KB Output is correct
7 Correct 343 ms 668 KB Output is correct
8 Correct 327 ms 592 KB Output is correct
9 Correct 338 ms 596 KB Output is correct
10 Correct 326 ms 596 KB Output is correct
11 Correct 360 ms 852 KB Output is correct
12 Correct 344 ms 592 KB Output is correct
13 Correct 264 ms 592 KB Output is correct
14 Correct 263 ms 544 KB Output is correct
15 Correct 262 ms 540 KB Output is correct
16 Correct 321 ms 852 KB Output is correct
17 Runtime error 132 ms 848 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 536 KB Output is correct
2 Correct 348 ms 532 KB Output is correct
3 Correct 331 ms 544 KB Output is correct
4 Correct 319 ms 536 KB Output is correct
5 Correct 335 ms 592 KB Output is correct
6 Correct 327 ms 668 KB Output is correct
7 Correct 291 ms 596 KB Output is correct
8 Correct 319 ms 852 KB Output is correct
9 Correct 339 ms 536 KB Output is correct
10 Correct 338 ms 664 KB Output is correct
11 Correct 382 ms 600 KB Output is correct
12 Correct 323 ms 596 KB Output is correct
13 Correct 325 ms 596 KB Output is correct
14 Execution timed out 3060 ms 8272 KB Time limit exceeded
15 Halted 0 ms 0 KB -