oj.uz

Submission #998061

# Submission time Handle Problem Language Result Execution time Memory
998061 2024-06-13T09:04:35 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) {
    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 (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 (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 (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 (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 (ans_nw < ans) {
            ans = ans_nw;
        }
    }
    return ans;
}

Answer get_ans(int n, vector<Point> a) {
    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;
        }
    }
    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 ()
            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 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 14 ms 1884 KB Output is correct
8 Correct 16 ms 1884 KB Output is correct
9 Correct 14 ms 1880 KB Output is correct
10 Correct 14 ms 1880 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 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 41 ms 6660 KB Output is correct
11 Correct 41 ms 6580 KB Output is correct
12 Correct 40 ms 6656 KB Output is correct
13 Correct 49 ms 6640 KB Output is correct
14 Correct 42 ms 6648 KB Output is correct
15 Correct 41 ms 6648 KB Output is correct
16 Correct 41 ms 6668 KB Output is correct
17 Correct 35 ms 6032 KB Output is correct
18 Correct 37 ms 5968 KB Output is correct
19 Correct 32 ms 5352 KB Output is correct
20 Correct 39 ms 5724 KB Output is correct
21 Correct 40 ms 6636 KB Output is correct
22 Correct 42 ms 6676 KB Output is correct
23 Correct 41 ms 6744 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 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 1 ms 600 KB Output is correct
13 Correct 0 ms 348 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 233 ms 548 KB Output is correct
2 Correct 227 ms 548 KB Output is correct
3 Correct 227 ms 532 KB Output is correct
4 Correct 234 ms 596 KB Output is correct
5 Correct 231 ms 536 KB Output is correct
6 Correct 228 ms 596 KB Output is correct
7 Correct 227 ms 596 KB Output is correct
8 Correct 232 ms 592 KB Output is correct
9 Correct 250 ms 792 KB Output is correct
10 Correct 239 ms 548 KB Output is correct
11 Correct 236 ms 552 KB Output is correct
12 Correct 256 ms 552 KB Output is correct
13 Correct 183 ms 604 KB Output is correct
14 Correct 180 ms 652 KB Output is correct
15 Correct 187 ms 548 KB Output is correct
16 Correct 183 ms 592 KB Output is correct
17 Correct 180 ms 544 KB Output is correct
18 Correct 217 ms 524 KB Output is correct
19 Correct 171 ms 596 KB Output is correct
20 Correct 175 ms 652 KB Output is correct
21 Incorrect 212 ms 596 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 552 KB Output is correct
2 Correct 228 ms 544 KB Output is correct
3 Correct 229 ms 540 KB Output is correct
4 Correct 228 ms 592 KB Output is correct
5 Correct 264 ms 592 KB Output is correct
6 Correct 236 ms 592 KB Output is correct
7 Correct 235 ms 592 KB Output is correct
8 Correct 227 ms 592 KB Output is correct
9 Correct 229 ms 592 KB Output is correct
10 Correct 229 ms 596 KB Output is correct
11 Correct 234 ms 668 KB Output is correct
12 Correct 236 ms 596 KB Output is correct
13 Correct 227 ms 668 KB Output is correct
14 Execution timed out 3041 ms 8264 KB Time limit exceeded
15 Halted 0 ms 0 KB -