oj.uz

Submission #464659

# Submission time Handle Problem Language Result Execution time Memory
464659 2021-08-13T15:33:24 Z Sarah_Mokhtar Cipele (COCI18_cipele) C++14
54 / 90
 156 ms 4060 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define read freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#define LESSGO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll N=1e6+10,M=505,OO=1e16,mod=1e9+7;
int n,m;
vector<ll>a,b;
bool ok(ll bound){
    int l=0;
    for(int i=0;i<n;++i){
        int idx=lower_bound(b.begin()+l,b.end(),a[i]-bound)-b.begin();
        if(b[idx]>a[i]){
            if(b[idx]-a[i]>bound) return 0;
        }
        l=idx+1;
    }
    return 1;
}
ll bs(){
    ll low=0,high=1e12,med;
    while(low<high){
        med=(low+high)>>1;
        if(ok(med)) high=med;
        else low=med+1;
    }
    return low;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;++i){
        ll x; cin>>x;
        a.push_back(x);
    }
    for(int i=0;i<m;++i){
        ll x; cin>>x;
        b.push_back(x);
    }
    if(n>m){
        swap(a,b);
        swap(n,m);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    cout<<bs()<<'\n';
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 2568 KB Output is correct
2 Correct 154 ms 3824 KB Output is correct

Subtask #2
0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 7 ms 440 KB Output is correct

Subtask #5
0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 10 ms 436 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 2364 KB Output is correct
2 Correct 102 ms 2532 KB Output is correct

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 2228 KB Output is correct
2 Incorrect 136 ms 4060 KB Output isn't correct