Submission #998104

#	Time	Username	Problem	Language	Result	Execution time	Memory
998104		piOOE	Izvanzemaljci (COI21_izvanzemaljci)	C++17	26 / 100	167 ms	3672 KiB

izvanzemaljci

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Answer {
    ll ans = 2e9 + 7;
    vector<vector<ll>> res;

    void norm(int k) {
        int t = 0;
        ll x = 2.5e9, y = 2.5e9;
        while (res.size() < k) {
            res.push_back({x, y, 1});
            t += 1;
            if (t & 1) {
                x = -x;
            }
            if (t & 2) {
                y = -y;
            }
        }
    }
};

void update(pair<ll, ll> &x, ll y) {
    x.first = min(x.first, y);
    x.second = max(x.second, y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<pair<ll, ll>> a(n);
    for (auto &[x, y] : a) {
        cin >> x >> y;
    }

    Answer ans{};
    ans.ans = 2e9 + 7;

    if (k >= 1) {
        ll minx = 2e9, maxx = -2e9, miny = 2e9, maxy = -2e9;
        for (auto &[x, y] : a) {
            minx = min(minx, x);
            maxx = max(maxx, x);
            miny = min(miny, y);
            maxy = max(maxy, y);
        }
        ll d = max({1LL, maxy - miny, maxx - minx});
        ans.ans = d;
        ans.res = {vector<ll>{minx, miny, d}};
    }

    if (k >= 2) {
        for (int t = 0; t < 2; ++t) {
            Answer now{};
            sort(a.begin(), a.end());
            vector<ll> mn(n + 1, 2e9), mx(n + 1, -2e9);
            for (int i = n - 1; i >= 0; --i) {
                mn[i] = min(mn[i + 1], a[i].second);
                mx[i] = max(mx[i + 1], a[i].second);
            }
            ll mny = 2e9, mxy = -2e9;
            for (int i = 0; i < n; ++i) {
                mny = min(mny, a[i].second);
                mxy = max(mxy, a[i].second);
                if (i + 1 < n && a[i + 1].first != a[i].first) {
                   ll d = max({1LL, mxy - mny, mx[i + 1] - mn[i + 1], a[i].first - a[0].first, a.back().first - a[i + 1].first});
                   if (now.ans > d) {
                       now.ans = d;
                       now.res.clear();
                       int rx = a[i].first;
                       int ry = mxy;
                       now.res.push_back({rx - d, ry - d, d});
                       int lx = a[i + 1].first;
                       int ly = mn[i + 1];
                       now.res.push_back({lx, ly, d});
                   }
                }
            }
            if (t == 1) {
                for (auto &f : now.res) {
                    swap(f[0], f[1]);
                }
            }
            if (ans.ans > now.ans) {
                ans = now;
            }
            for (auto &[x, y]: a) {
                swap(x, y);
            }
        }
    }

    if (k >= 3) {
        for (int swp = 0; swp < 2; ++swp) {
            for (int neg = 0; neg < 2; ++neg) {
                sort(a.begin(), a.end());
                Answer now{};
                ll mny = 2e9, mxy = -2e9;
                for (int pref = 0; pref < n - 2; ++pref) {
                    mny = min(mny, a[pref].second);
                    mxy = max(mxy, a[pref].second);
                    ll dnow = max({1LL, mxy - mny, a[pref].first - a[0].first});
                    if (a[pref + 1].first != a[pref].first) {
                        // case 1: sandwich
                        pair<ll, ll> Y{2e9, -2e9};
                        vector<pair<ll, ll>> suf(n + 1, pair<ll, ll>(2e9, -2e9));
                        for (int i = n - 1; i >= 0; --i) {
                            suf[i] = suf[i + 1];
                            update(suf[i], a[i].second);
                        }
                        for (int m = pref + 1; m + 1 < n; ++m) {
                            update(Y, a[m].second);
                            if (a[m + 1].first != a[m].first && Y.second - Y.first <= a[m].first - a[pref + 1].first) {
                                ll dr = max({1LL, suf[m + 1].second - suf[m + 1].first, a[n - 1].first - a[m + 1].first});
                                ll dm = max({1LL, Y.second - Y.first, a[m].first - a[pref + 1].first});
                                ll D = max({dm, dr, dnow});
                                if (now.ans > D) {
                                    now.ans = D;
                                    now.res.clear();
                                    now.res.push_back({a[pref].first - dnow, mxy - dnow, dnow});
                                    now.res.push_back({a[pref + 1].first, Y.first, dm});
                                    now.res.push_back({a[m + 1].first, suf[m + 1].first, dr});
                                }
                            }
                        }
                        // case 2: not sandwich
                        sort(a.begin() + pref + 1, a.end(), [&](auto u, auto v) {
                            return u.second < v.second;
                        });
                        pair<ll, ll> X = {2e9, -2e9};
                        fill(suf.begin(), suf.end(), pair<ll, ll>(2e9, -2e9));
                        for (int i = n - 1; i >= 0; --i) {
                            suf[i] = suf[i + 1];
                            update(suf[i], a[i].first);
                        }
                        for (int m = pref + 1; m + 1 < n; ++m) {
                            update(X, a[m].first);
                            ll dm = max({1LL, X.second - X.first, a[m].second - a[pref + 1].second});
                            ll dr = max({1LL, suf[m + 1].second - suf[m + 1].first, a[n - 1].second - a[m + 1].second});
                            if (a[m].second != a[m + 1].second) {
                                ll D = max({dnow, dm, dr});
                                if (now.ans > D) {
                                    now.ans = D;
                                    now.res.clear();
                                    now.res.push_back({a[pref].first - dnow, mxy - dnow, dnow});
                                    now.res.push_back({X.first, a[m].second - dm, dm});
                                    now.res.push_back({suf[m + 1].first, a[m + 1].second, dr});
                                }
                            }
                        }

                        sort(a.begin() + pref + 1, a.end());

                    }
                    if (now.ans < ans.ans) {
                        ans = now;
                        for (auto &f : ans.res) {
                            if (neg) {
                                f[0] = -f[0];
                            }
                            if (swp) {
                                swap(f[0], f[1]);
                            }
                        }
                    }
                }
                for (auto &[x, y] : a) {
                    x = -x;
                }
            }
            for (auto &[x, y] : a) {
                swap(x, y);
            }
        }
    }

    ans.norm(k);

    for (auto &t : ans.res) {
        for (auto x : t) {
            cout << x << " ";
        }
        cout << '\n';
    }

    return 0;
}

Compilation message (stderr)

izvanzemaljci.cpp: In member function 'void Answer::norm(int)':
izvanzemaljci.cpp:13:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |         while (res.size() < k) {
      |                ~~~~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 21 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32