Submission #922338

# Submission time Handle Problem Language Result Execution time Memory
922338 2024-02-05T12:21:55 Z sleepntsheep Cipele (COCI18_cipele) C++17
90 / 90
37 ms 1116 KB
#include <iostream>
#include <climits>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using u32 = unsigned;
using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
using pt = complex<f80>;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

int n, m, a_[N], b_[N], *a = a_, *b = b_, z = INT_MAX;

int main()
{
    ShinLena;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    if (n > m) swap(n, m), swap(a, b);
    sort(a, a+n), sort(b, b+m);

    auto bad = [&](int x) {
        int p = 0;
        for (int i = 0; i < n; ++i)
        {
            while (p < m and abs(b[p] - a[i]) > x) ++p;
            if (p == m) return 1;
            ++p;
        }
        return 0;
    };

    int l = 0, r = 1e9;
    while (l <= r)
    {
        int m = (l+r)/2;
        if (bad(m)) l = m + 1;
        else r = m - 1;
    }
    cout << r + 1;
    return 0;
}


# Verdict Execution time Memory Grader output
1 Correct 22 ms 1112 KB Output is correct
2 Correct 31 ms 1116 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 37 ms 1112 KB Output is correct
2 Correct 36 ms 1116 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 37 ms 1116 KB Output is correct
2 Correct 25 ms 916 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 35 ms 1116 KB Output is correct
2 Correct 20 ms 1040 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 36 ms 856 KB Output is correct
2 Correct 29 ms 1116 KB Output is correct