oj.uz

Submission #313508

# Submission time Handle Problem Language Result Execution time Memory
313508 2020-10-16T06:32:00 Z balbit Cipele (COCI18_cipele) C++14
90 / 90
 50 ms 2936 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2688 KB Output is correct
2 Correct 46 ms 2936 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2936 KB Output is correct
2 Correct 46 ms 2936 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 504 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2424 KB Output is correct
2 Correct 27 ms 1792 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2680 KB Output is correct
2 Correct 22 ms 2048 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2416 KB Output is correct
2 Correct 39 ms 2552 KB Output is correct