oj.uz

Submission #884341

# Submission time Handle Problem Language Result Execution time Memory
884341 2023-12-07T07:30:14 Z noiaint Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 17 ms 16732 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, k;
pair<int, int> a[N];

namespace task1 {

void solve() {
    int maxx, maxy, minx, miny;
    maxx = maxy = -oo;
    minx = miny = oo;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        tie(x, y) = a[i];
        maxi(maxx, x);
        maxi(maxy, y);
        mini(minx, x);
        mini(miny, y);
    }

    int w = maxx - minx;
    int h = maxy - miny;

    int l = max(w, h);
    l = max(l, 1LL);

    debug(w, h);

    cout << minx << ' ' << miny << ' ' << l;

}

}

namespace task2 {

int pre_min_x[N], pre_min_y[N], pre_max_x[N], pre_max_y[N];
int suf_min_x[N], suf_min_y[N], suf_max_x[N], suf_max_y[N];

array<int, 3> res[3];

void solve() {

    sort(a + 1, a + n + 1);

    pre_min_x[0] = pre_min_y[0] = suf_min_x[n + 1] = suf_min_y[n + 1] = ooo;
    pre_max_x[0] = pre_max_y[0] = suf_max_x[n + 1] = suf_max_y[n + 1] = -ooo;

    for (int i = 1; i <= n; ++i) {
        int x, y;
        tie(x, y) = a[i];

        pre_min_x[i] = min(pre_min_x[i - 1], x);
        pre_max_x[i] = max(pre_max_x[i - 1], x);
        pre_min_y[i] = min(pre_min_y[i - 1], y);
        pre_max_y[i] = max(pre_max_y[i - 1], y);
    }
    for (int i = n; i >= 1; --i) {
        int x, y;
        tie(x, y) = a[i];

        suf_min_x[i] = min(suf_min_x[i + 1], x);
        suf_max_x[i] = max(suf_max_x[i + 1], x);
        suf_min_y[i] = min(suf_min_y[i + 1], y);
        suf_max_y[i] = max(suf_max_y[i + 1], y);
    }

    res[0][2] = res[1][2] = ooo;

    for (int i = 1; i < n; ++i) {
        // first photo
        int l1 = max({1LL, pre_max_x[i] - pre_min_x[i], pre_max_y[i] - pre_min_y[i]});
        int x1 = pre_min_x[i];
        int y1 = pre_min_y[i];

        // second photo
        int l2 = max({1LL, suf_max_x[i + 1] - suf_min_x[i + 1], suf_max_y[i + 1] - suf_min_y[i + 1]});
        int x2 = suf_min_x[i + 1];
        int y2 = suf_min_y[i + 1];

        // get best
        if (max(l1, l2) < max(res[0][2], res[1][2])) {
            res[0] = {x1, y1, l1};
            res[1] = {x2, y2, l2};
        }
    }

    for (int i = 0; i < 2; ++i) {
        for (int x : res[i]) cout << x << ' ';
        cout << '\n';
    }
}

}

void process() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;

    if (k == 1) {task1::solve(); return;}
    if (k == 2) {task2::solve(); return;}
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #else
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    #endif

    int tc = 1;
    // cin >> tc;

    while (tc--) {
        process();
    }

    return 0;
}

/*

*/

Compilation message

izvanzemaljci.cpp: In function 'void task1::solve()':
izvanzemaljci.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
izvanzemaljci.cpp:70:5: note: in expansion of macro 'debug'
   70 |     debug(w, h);
      |     ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 16 ms 4444 KB Output is correct
8 Correct 17 ms 4444 KB Output is correct
9 Correct 17 ms 4564 KB Output is correct
10 Correct 16 ms 4560 KB Output is correct
11 Correct 16 ms 4444 KB Output is correct

Subtask #2
0 / 21.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 32.0

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