Submission #1003667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003667		ThegeekKnight16	Izvanzemaljci (COI21_izvanzemaljci)	C++17	0 / 100	3042 ms	856 KiB

izvanzemaljci

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;


void solve1(int N, int K)
{
    int x11 = INF, x12 = -INF, y11 = INF, y12 = -INF;
    for (int i = 0; i < N; i++)
    {
        int X, Y;
        cin >> X >> Y;
        x11 = min(x11, X);
        x12 = max(x12, X);
        y11 = min(y11, Y);
        y12 = max(y12, Y);
    }

    int l = max(x12 - x11, y12 - y11);
    cout << x11 << " " << y11 << " " << l << '\n';
}
void solve2(int N, int K)
{

}

void bt(int id, tuple<int, int, int, int> q1, tuple<int, int, int, int> q2, tuple<int, int, int, int> q3, int &resp, vector<tuple<int, int, int>> &ans, const vector<pair<int, int>> &v)
{
    if (id == v.size())
    {
        auto [x11, x12, y11, y12] = q1;
        auto [x21, x22, y21, y22] = q2;
        auto [x31, x32, y31, y32] = q3;
        if (x11 > x12) x11 = -INF, x12 = -INF+1, y11 = -INF, y12 = -INF+1;
        if (x21 > x22) x21 = INF, x22 = INF+1, y21 = -INF, y22 = -INF+1;
        if (x31 > x32) x31 = INF, x32 = INF+1, y31 = INF, y32 = INF+1;
        int l1 = max(x12 - x11, y12 - y11); x12 = x11 + l1, y12 = y11 + l1;
        int l2 = max(x22 - x21, y22 - y21); x22 = x21 + l2, y22 = y21 + l2;
        int l3 = max(x32 - x31, y32 - y31); x32 = x31 + l3, y32 = y31 + l3;
        if (max({l1, l2, l3}) > resp) return;
        bool interX12 = (min(x11, x21) <= max(x11, x21) && max(x11, x21) <= min(x12, x22)) || (min(x11, x21) <= min(x12, x22) && min(x12, x22) <= max(x11, x21));
        bool interX13 = (min(x11, x31) <= max(x11, x31) && max(x11, x31) <= min(x12, x32)) || (min(x11, x31) <= min(x12, x32) && min(x12, x32) <= max(x11, x31));
        bool interX23 = (min(x21, x31) <= max(x21, x31) && max(x21, x31) <= min(x21, x32)) || (min(x21, x31) <= min(x22, x32) && min(x22, x32) <= max(x21, x31));
        bool interY12 = (min(y11, y21) <= max(y11, x21) && max(y11, y21) <= min(y12, x22)) || (min(y11, y21) <= min(y12, y22) && min(y12, y22) <= max(y11, y21));
        bool interY13 = (min(y11, y31) <= max(y11, x31) && max(y11, y31) <= min(y12, x32)) || (min(y11, y31) <= min(y12, y32) && min(y12, y32) <= max(y11, y31));
        bool interY23 = (min(y21, y31) <= max(y21, x31) && max(y21, y31) <= min(y21, x32)) || (min(y21, y31) <= min(y22, y32) && min(y22, y32) <= max(y21, y31));
        if (interX12 && interY12) return;
        if (interX13 && interY13) return;
        if (interX23 && interY23) return;
        resp = max({l1, l2, l3});
        ans[0] = make_tuple(x11, y11, l1);
        ans[1] = make_tuple(x21, y21, l2);
        ans[2] = make_tuple(x31, y31, l3);
        return;
    }

    auto [x11, x12, y11, y12] = q1;
    auto [x21, x22, y21, y22] = q2;
    auto [x31, x32, y31, y32] = q3;

    auto [X, Y] = v[id];
    bt(id+1, make_tuple(min(x11, X), max(x12, X), min(y11, Y), max(y12, Y)), q2, q3, resp, ans, v);
    bt(id+1, q1, make_tuple(min(x21, X), max(x22, X), min(y21, Y), max(y22, Y)), q3, resp, ans, v);
    bt(id+1, q1, q2, make_tuple(min(x31, X), max(x32, X), min(y31, Y), max(y32, Y)), resp, ans, v);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    if (K == 1) {solve1(N, K); return 0;}
    else if (K == 2) {solve2(N, K); return 0;}

    vector<pair<int, int>> v(N); for (auto &[x, y] : v) cin >> x >> y;
    int resp = INF; vector<tuple<int, int, int>> ans(3);
    bt(0, make_tuple(INF, -INF, INF, -INF), make_tuple(INF, -INF, INF, -INF), make_tuple(INF, -INF, INF, -INF), resp, ans, v);
    for (auto x : ans)
        cout << get<0>(x) << " " << get<1>(x) << " " << get<2>(x) << '\n';
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'void bt(int, std::tuple<int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int, int>, int&, std::vector<std::tuple<int, int, int> >&, const std::vector<std::pair<int, int> >&)':
izvanzemaljci.cpp:29:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     if (id == v.size())
      |         ~~~^~~~~~~~~~~

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