Submission #520554

#	Time	Username	Problem	Language	Result	Execution time	Memory
520554		Vimmer	Izvanzemaljci (COI21_izvanzemaljci)	C++14	5 / 100	21 ms	1876 KiB

izvanzemaljci

#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")

#define F first
#define S second
#define PB push_back
#define M ll(1e9 + 7)
#define sz(x) (ll)x.size()
#define N 1000500
#define pri(x) cout << x << endl
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

using namespace std;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;

bool inter(ll x1, ll y1, ll l1, ll x2, ll y2, ll l2)
{
    if (x1 + l1 < x2)
        return 0;

    if (x2 + l2 < x1)
        return 0;

    if (y1 + l1 < y2)
        return 0;

    if (y2 + l2 < y1)
        return 0;

    return 1;
}

int main()
{
    istream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n, k;

    cin >> n >> k;

    ll x[n], y[n];

    for (ll i = 0; i < n; i++)
        cin >> x[i] >> y[i];

    if (k == 1)
    {
        ll mxx = -1e18, mnx = 1e18, mxy = -1e18, mny = 1e18;

        for (int i = 0; i < n; i++)
        {
            mxx = max(mxx, x[i]);

            mxy = max(mxy, y[i]);

            mnx = min(mnx, x[i]);

            mny = min(mny, y[i]);
        }

        ll len = max(mxx - mnx, mxy - mny);

        pri(mnx _ mny _ max(1ll, len));

        exit(0);
    }

    if (k == 3)
    {
        ll best = 1e18;

        ll x1, y1, x2, y2, x3, y3, l1, l2, l3;

        for (int msk = 0; msk < (1 << n); msk++)
        {
            for (int nmsk = 0; nmsk < (1 << n); nmsk++)
            {
                bool bad = 0;

                if (__builtin_popcount(msk & nmsk) != 0)
                    continue;

                ll mxx1 = -1e18, mnx1 = 1e18, mxy1 = -1e18, mny1 = 1e18;

                ll mxx2 = -1e18, mnx2 = 1e18, mxy2 = -1e18, mny2 = 1e18;

                ll mxx3 = -1e18, mnx3 = 1e18, mxy3 = -1e18, mny3 = 1e18;

                for (int i = 0; i < n; i++)
                {
                    if ((1 << i) & msk)
                    {
                        mxx1 = max(mxx1, x[i]);

                        mxy1 = max(mxy1, y[i]);

                        mnx1 = min(mnx1, x[i]);

                        mny1 = min(mny1, y[i]);
                    }
                    else if ((1 << i) & nmsk)
                    {
                        mxx2 = max(mxx2, x[i]);

                        mxy2 = max(mxy2, y[i]);

                        mnx2 = min(mnx2, x[i]);

                        mny2 = min(mny2, y[i]);
                    }
                    else
                    {
                        mxx3 = max(mxx3, x[i]);

                        mxy3 = max(mxy3, y[i]);

                        mnx3 = min(mnx3, x[i]);

                        mny3 = min(mny3, y[i]);
                    }
                }

                if (mxx1 == -1e18)
                {
                    mxx1 = mny1 = mxy1 = mnx1 = ll(2e9);
                }

                if (mxx2 == -1e18)
                {
                    mxx2 = mny2 = mxy2 = mnx2 = ll(-2e9);
                }

                if (mxx3 == -1e18)
                {
                    mxx3 = mny3 = mxy3 = mnx3 = ll(3e9);
                }

                ll len1 = max(1ll, max(mxx1 - mnx1, mxy1 - mny1));
                ll len2 = max(1ll, max(mxx2 - mnx2, mxy2 - mny2));
                ll len3 = max(1ll, max(mxx3 - mnx3, mxy3 - mny3));

//                pri("lol");

                if (max(len1, max(len2, len3)) >= best)
                    continue;

                if (inter(mnx1, mny1, len1, mnx2, mny2, len2))
                    continue;

                if (inter(mnx3, mny3, len3, mnx2, mny2, len2))
                    continue;

                if (inter(mnx1, mny1, len1, mnx3, mny3, len3))
                    continue;

                x1 = mnx1; y1 = mny1; l1 = len1;
                x2 = mnx2; y2 = mny2; l2 = len2;
                x3 = mnx3; y3 = mny3; l3 = len3;

                best = max(len1, max(len2, len3));
            }
        }

        if (best == 1e18)
            assert(0);

        pri(x1 _ y1 _ l1);
        pri(x2 _ y2 _ l2);
        pri(x3 _ y3 _ l3);

        exit(0);
    }
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:90:22: warning: unused variable 'bad' [-Wunused-variable]
   90 |                 bool bad = 0;
      |                      ^~~

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