Submission #313508

#	Time	Username	Problem	Language	Result	Execution time	Memory
313508		balbit	Cipele (COCI18_cipele)	C++14	90 / 90	50 ms	2936 KiB

cipele

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0)
#define endl '\n'
#endif // BALBIT

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

const int maxn = 5005;
ll dp[maxn][maxn];
int a[maxn], b[maxn];

signed main(){
    IOS();
    int n,m; cin>>n>>m;
    vector<int> a(n), b(m);
    for (int i = 0; i<n; ++i) {
        cin>>a[i];
    }
    sort(ALL(a));
    for (int j = 0; j<m; ++j) {
        cin>>b[j];
    }
    sort(ALL(b));
    if (n > m) {
        swap(a,b); swap(n,m);
    }
//    return 0;
    int l = 0, r = 1e9+1;
    while (l != r) {
        int X = (l+r)/2;
        int j = 0;
        for (int i = 0; i<n; ++i)  {
            while (j < m && abs(a[i] - b[j]) > X) {
                ++j;
            }
            if (j >= m) {
                l = X+1;
                goto outo;
            }
            ++j;
        }
        r = X;
        outo:;
    }
    cout<<l<<endl;
}
/*
5 5
7 6 1 2 10
9 11 6 3 12
*/

• 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