oj.uz

Submission #160326

# Submission time Handle Problem Language Result Execution time Memory
160326 2019-10-27T02:34:30 Z bloxblox Cipele (COCI18_cipele) C++14
18 / 90
 65 ms 2980 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
#define vi vector<long long>
#define pi pair<long long, long long>
#define mp make_pair
#define endl '\n'
#define _ << ' '
#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))
#define clog2(x) (((x) - (1 << FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> idxset;
//find_by_order(i) : iterator to the value at index i, order_of_key(x) : the index of value x
const ll mod = (ll)1e9+7;
const ll INF = (ll)1234567890;
const ll N = (1<<5);

int n, m, a[100001], b[100001], ans = INF;

bool check(int x){
    int i=0;
    for(int j=0; j<m; j++){
        if(abs(a[i]-b[j])<=x) i++;
        if(i==n) return 1;
    }
    return (i==n?1:0);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    //freopen("C.txt", "r", stdin);
    #endif
    cin >> n >> m;
    if(n<m){
        for(int i=0; i<n; i++){
            cin >> a[i];
        }
        for(int i=0; i<m; i++){
            cin >> b[i];
        }
    }
    else{
        for(int i=0; i<n; i++){
            cin >> b[i];
        }
        for(int i=0; i<m; i++){
            cin >> a[i];
        }
        swap(n, m);
    }
    sort(a, a+n);
    sort(b, b+n);
    int lb = 0, rb = 1100000100;
    while(lb<rb){
        int mid = (lb+rb)/2;
        if(check(mid)){
            ans = min(ans, mid);
            rb = mid;
        }
        else{
            lb = mid + 1;
        }
    }
    cout << ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2680 KB Output is correct
2 Correct 65 ms 2940 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 5 ms 504 KB Output isn't correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 2488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 2428 KB Output isn't correct
2 Halted 0 ms 0 KB -