oj.uz

Submission #520546

# Submission time Handle Problem Language Result Execution time Memory
520546 2022-01-30T08:52:38 Z Vimmer Izvanzemaljci (COI21_izvanzemaljci) C++14
5 / 100
 103 ms 1872 KB 
#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;

                for (int i = 0; i < n; i++)
                    if ((1 << i) & msk)
                     if ((1 << i) & nmsk)
                        bad = 1;

                if (bad)
                    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 = 1e9 + 1e9;
                }

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

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

                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));

                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 == 0)
            assert(0);

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

        exit(0);
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 20 ms 1868 KB Output is correct
8 Correct 20 ms 1868 KB Output is correct
9 Correct 20 ms 1868 KB Output is correct
10 Correct 20 ms 1868 KB Output is correct
11 Correct 19 ms 1872 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Integer 5085241283009 violates the range [-3*10^9, 3*10^9]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 204 KB Integer 5085241283009 violates the range [-3*10^9, 3*10^9]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 300 KB Integer 5085241283009 violates the range [-3*10^9, 3*10^9]
2 Halted 0 ms 0 KB -