oj.uz

Submission #464662

# Submission time Handle Problem Language Result Execution time Memory
464662 2021-08-13T15:51:36 Z Sarah_Mokhtar Cipele (COCI18_cipele) C++14
54 / 90
 156 ms 2600 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]||idx==m){
            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 144 ms 2540 KB Output is correct
2 Correct 156 ms 2524 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 2600 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 8 ms 332 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 332 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 428 KB Output is correct
2 Correct 7 ms 332 KB Output is correct

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 2312 KB Output is correct
2 Correct 82 ms 1496 KB Output is correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 2428 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 2288 KB Output is correct
2 Incorrect 126 ms 2468 KB Output isn't correct