Submission #99161

#TimeUsernameProblemLanguageResultExecution timeMemory
99161M_H_H_7Cipele (COCI18_cipele)C++14
90 / 90
357 ms4340 KiB
//In The Name of Beauty #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vll; #define IB std::ios::sync_with_stdio(0); #define pb(x) push_back(x); #define mp(x,y) make_pair(x,y) #define pll pair<ll,ll> #define F first #define S second ll const MAXN = 1e5 + 8; ll const INF = 1e9; ll const delta = 1000000007; vll a , b; ll n , m; bool mar[MAXN]; bool check(ll x) { ll last = m; for(ll i = n - 1;i >= 0;i--){ ll r = upper_bound(b.begin(),b.end(),a[i] + x) - b.begin() - 1; ll l = lower_bound(b.begin(),b.end(),a[i] - x) - b.begin(); if(l > r)return 0; if(l > last - 1)return 0; last = min(last - 1,r); } return 1; } int main() { IB; cin.tie(0); cout.tie(0); cin >> n >> m; ll t; for(ll i = 0;i < n;i++){ cin >> t; a.pb(t); } for(ll i = 0;i < m;i++){ cin >> t; b.pb(t); } if(a.size() > b.size()){ swap(a,b); swap(n,m); } sort(a.begin(),a.end()); sort(b.begin(),b.end()); ll l = 0 , r = INF , mid = (l + r) / 2; while(r - l > 1){ if(check(mid))r = mid; else l = mid; mid = (l + r) / 2; } if(check(l))return cout << l,0; cout << r; return 0; } //Written by M_H_H_7
#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...