Submission #916560

#	Time	Username	Problem	Language	Result	Execution time	Memory
916560		406	Cipele (COCI18_cipele)	C++17	90 / 90	42 ms	3796 KiB

cipele

#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;

const int64_t INF = 1ll << 60;
const int N = 1e5 + 5;
vector<int> L, R;
int n, m;

bool check(int x) {
       int p = 0;
       FOR(i, 0, n) {
                while (p < m && abs(R[p] - L[i]) > x) ++p;
                if (p == m) return false;
                ++p;
       }
       return true;
}

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> m;
        L.resize(n); R.resize(m);
        for (auto &i: L) cin >> i;
        for (auto &i: R) cin >> i;
        if (n > m) {
                swap(n, m);
                swap(L, R);
        }
        sort(L.begin(), L.end());
        sort(R.begin(), R.end());

        int l = -1, r = INF;
        while (l + 1 < r) {
                int m = l + r >> 1;
                if (check(m)) r = m;
                else l = m;
        }
        cout << r << '\n';
        return 0;
}

Compilation message (stderr)

cipele.cpp: In function 'int main()':
cipele.cpp:39:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |                 int m = l + r >> 1;
      |                         ~~^~~

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9