Submission #472432

#TimeUsernameProblemLanguageResultExecution timeMemory
472432_L__Cipele (COCI18_cipele)C++17
90 / 90
356 ms1864 KiB
// This code is written by _L__ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>; #define endl '\n' #define F_word ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); typedef long long ll; typedef long double ld; const ll mod = 1e9+7, N = 1e5+300, inf = 1e18; const ld E = 1e-6; #define ff first #define ss second ll a[N], b[N], n, m; bool check(ll mid){ ll cnt = 0; ll cur = 0-1; if(n<=m){ for(int i = 0; i < n; ++i){ ll l = lower_bound(b, b+m, a[i]-mid)-b; ll r = upper_bound(b, b+m, a[i]+mid)-b-1; if(l>r)return 0; if(cur+1 <= r){cur = max(l, cur+1); ++cnt;} } return (cnt >= n); } else { for(int i = 0; i < m; ++i){ ll l = lower_bound(a, a+n, b[i]-mid)-a; ll r = upper_bound(a, a+n, b[i]+mid)-a-1; if(l>r) return 0; if(cur+1 <= r){cur = max(l, cur+1); ++cnt;} } return (cnt>=m); } } ll lower(){ ll l = 0, r = 1e11, ans = 0; while(l <= r){ ll mid = (l+r)/2; if(check(mid)){ ans = mid; r = mid-1; } else l = mid+1; } return ans; } int main(void){ F_word; cin >> n >> m; for(int i = 0; i < n; ++i) cin >> a[i]; for(int i = 0; i < m; ++i) cin >> b[i]; sort(a, a+n); sort(b, b+m); cout << lower() << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...