Submission #997975

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
997975	2024-06-13T07:25:53 Z	arbuzick	Izvanzemaljci (COI21_izvanzemaljci)	C++17	Compilation error	0 ms	0 KB

izvanzemaljci

#include <bits/stdc++.h>
#define int long long

using namespace std;

constexpr long long inf = (long long)1e18 + 7;

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 get_ans(int n, vector<Point> a) {
    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]));
        ans_nw.add(Point(a[i].x - side1, pr_mn[i + 1]), side1);
        int side2 = max(1LL, max(a[n - 1].x - a[i + 1].x, suf_mx[i + 1] - suf_mn[i + 1]));
        ans_nw.add(Point(a[i + 1].x, suf_mn[i + 1]), side2);
        if (ans_nw < ans) {
            ans = ans_nw;
        }
    }
    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(1, max(mx_x - mn_x, mx_y - mn_y)) << '\n';
    } else if (k == 2) {
        if (n == 1) {
            cout << a[0].x << ' ' << a[0].y << ' ' << 1 << '\n';
            cout << a[0].x + 2 << ' ' << a[0].y + 2 << ' ' << 1 << '\n';
            return;
        }
        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);
        }
        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;
}

Compilation message

izvanzemaljci.cpp: In function 'void solve()':
izvanzemaljci.cpp:80:83: error: no matching function for call to 'max(int, const long long int&)'
   80 |         cout << mn_x << ' ' << mn_y << ' ' << max(1, max(mx_x - mn_x, mx_y - mn_y)) << '\n';
      |                                                                                   ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from izvanzemaljci.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
izvanzemaljci.cpp:80:83: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   80 |         cout << mn_x << ' ' << mn_y << ' ' << max(1, max(mx_x - mn_x, mx_y - mn_y)) << '\n';
      |                                                                                   ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from izvanzemaljci.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
izvanzemaljci.cpp:80:83: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   80 |         cout << mn_x << ' ' << mn_y << ' ' << max(1, max(mx_x - mn_x, mx_y - mn_y)) << '\n';
      |                                                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from izvanzemaljci.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
izvanzemaljci.cpp:80:83: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   80 |         cout << mn_x << ' ' << mn_y << ' ' << max(1, max(mx_x - mn_x, mx_y - mn_y)) << '\n';
      |                                                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from izvanzemaljci.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
izvanzemaljci.cpp:80:83: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   80 |         cout << mn_x << ' ' << mn_y << ' ' << max(1, max(mx_x - mn_x, mx_y - mn_y)) << '\n';
      |                                                                                   ^