Submission #998086

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998086	2024-06-13T09:32:31 Z	arbuzick	Izvanzemaljci (COI21_izvanzemaljci)	C++17	68 / 100	3000 ms	8264 KB

izvanzemaljci

#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 = min(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	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	1 ms	348 KB	Output is correct
7	Correct	19 ms	1884 KB	Output is correct
8	Correct	15 ms	1884 KB	Output is correct
9	Correct	18 ms	1884 KB	Output is correct
10	Correct	15 ms	1880 KB	Output is correct
11	Correct	15 ms	1884 KB	Output is correct

Subtask #2

21.0 / 21.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	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	47 ms	6648 KB	Output is correct
11	Correct	44 ms	6748 KB	Output is correct
12	Correct	44 ms	6656 KB	Output is correct
13	Correct	43 ms	6644 KB	Output is correct
14	Correct	44 ms	6640 KB	Output is correct
15	Correct	58 ms	6644 KB	Output is correct
16	Correct	82 ms	6644 KB	Output is correct
17	Correct	42 ms	6044 KB	Output is correct
18	Correct	37 ms	5976 KB	Output is correct
19	Correct	34 ms	5464 KB	Output is correct
20	Correct	36 ms	5724 KB	Output is correct
21	Correct	43 ms	6648 KB	Output is correct
22	Correct	48 ms	6672 KB	Output is correct
23	Correct	45 ms	6644 KB	Output is correct

Subtask #3

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 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	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	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	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	452 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	604 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	262 ms	664 KB	Output is correct
2	Correct	269 ms	536 KB	Output is correct
3	Correct	271 ms	664 KB	Output is correct
4	Correct	264 ms	592 KB	Output is correct
5	Correct	261 ms	536 KB	Output is correct
6	Correct	266 ms	532 KB	Output is correct
7	Correct	277 ms	592 KB	Output is correct
8	Correct	268 ms	600 KB	Output is correct
9	Correct	263 ms	596 KB	Output is correct
10	Correct	276 ms	856 KB	Output is correct
11	Correct	326 ms	592 KB	Output is correct
12	Correct	277 ms	668 KB	Output is correct
13	Correct	207 ms	592 KB	Output is correct
14	Correct	206 ms	596 KB	Output is correct
15	Correct	215 ms	652 KB	Output is correct
16	Correct	228 ms	592 KB	Output is correct
17	Correct	224 ms	848 KB	Output is correct
18	Correct	231 ms	796 KB	Output is correct
19	Correct	199 ms	548 KB	Output is correct
20	Correct	208 ms	596 KB	Output is correct
21	Correct	252 ms	592 KB	Output is correct
22	Correct	237 ms	596 KB	Output is correct
23	Correct	197 ms	596 KB	Output is correct
24	Correct	212 ms	592 KB	Output is correct

Subtask #5

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	263 ms	596 KB	Output is correct
2	Correct	285 ms	848 KB	Output is correct
3	Correct	261 ms	596 KB	Output is correct
4	Correct	263 ms	536 KB	Output is correct
5	Correct	268 ms	556 KB	Output is correct
6	Correct	268 ms	540 KB	Output is correct
7	Correct	295 ms	852 KB	Output is correct
8	Correct	260 ms	596 KB	Output is correct
9	Correct	261 ms	592 KB	Output is correct
10	Correct	269 ms	592 KB	Output is correct
11	Correct	264 ms	552 KB	Output is correct
12	Correct	266 ms	592 KB	Output is correct
13	Correct	261 ms	600 KB	Output is correct
14	Execution timed out	3020 ms	8264 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-