oj.uz

Submission #464663

# Submission time Handle Problem Language Result Execution time Memory
464663 2021-08-13T15:52:14 Z Sarah_Mokhtar Cipele (COCI18_cipele) C++14
90 / 90
 174 ms 2624 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(idx==m) return 0;
        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 142 ms 2580 KB Output is correct
2 Correct 174 ms 2608 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 2484 KB Output is correct
2 Correct 152 ms 2624 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 7 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 8 ms 404 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2288 KB Output is correct
2 Correct 83 ms 1484 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 2420 KB Output is correct
2 Correct 126 ms 1868 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 2348 KB Output is correct
2 Correct 137 ms 2468 KB Output is correct