Submission #998074

#	Time	Username	Problem	Language	Result	Execution time	Memory
998074		piOOE	Izvanzemaljci (COI21_izvanzemaljci)	C++17	5 / 100	31 ms	1996 KiB

izvanzemaljci

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Answer {
    int 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;
            }
        }
    }
};

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

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

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

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

    if (k >= 1) {
        int 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);
        }
        int d = max({1, 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<int> 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);
            }
            int 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) {
                   int d = max({1, 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);
            }
        }
    }

    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: 0 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32