oj.uz

Submission #472516

# Submission time Handle Problem Language Result Execution time Memory
472516 2021-09-13T16:50:04 Z HossamHero7 Cipele (COCI18_cipele) C++14
90 / 90
 154 ms 2476 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define endl '\n'
int n,m;
vector <int> v1;
vector <int> v2;
bool valid(int dif){
    int curStart = 0;
    for(int i=0;i<n;i++){
        int idx = lower_bound(v2.begin()+curStart,v2.end(),v1[i]-dif) - v2.begin();
        if(idx == m) return 0;
        if(abs(v2[idx] - v1[i]) > dif) return 0;
        curStart = idx + 1;
    }
    return 1;
}
void solve(){
   cin>>n>>m;
   v1.resize(n);
   v2.resize(m);
   for(auto &i:v1) cin>>i;
   for(auto &i:v2) cin>>i;
    if(n>m){
        swap(n,m);
        swap(v1,v2);
    }
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    int l=0;
    int r=1e9;
    int ans=0;
    while(l<=r){
        int md = l + r >> 1;
        if(valid(md)){
            ans = md;
            r = md - 1;
        }
        else l = md + 1;
    }
    cout<<ans<<endl;
}
int main()
{
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

cipele.cpp: In function 'void solve()':
cipele.cpp:35:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int md = l + r >> 1;
      |                  ~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 972 KB Output is correct
2 Correct 154 ms 1068 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 1064 KB Output is correct
2 Correct 140 ms 1060 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Output is correct
2 Correct 7 ms 432 KB Output is correct

Subtask #6
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 844 KB Output is correct
2 Correct 82 ms 1756 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 980 KB Output is correct
2 Correct 81 ms 1988 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 908 KB Output is correct
2 Correct 121 ms 2476 KB Output is correct