Submission #894403

#TimeUsernameProblemLanguageResultExecution timeMemory
894403vjudge1Cipele (COCI18_cipele)C++17
18 / 90
62 ms10060 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> using namespace std; //using namespace __gnu_pbds; #define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define russian setlocale(LC_ALL,"Russian_Russia.20866"); #define file freopen("condense2.in", "r", stdin), freopen("condense2.out", "w", stdout); #define ll long long #define ull unsigned long long #define ld long double #define pll pair<ll, ll> #define pii pair<int, int> #define pli pair<ll, int> #define all(s) s.begin(), s.end() #define pb push_back #define ins insert #define mp make_pair #define sz(x) x.size() #define F first #define S second #define lb lower_bound #define ub upper_bound #define mem(x) memset(x, 0, sizeof(x)) const ll N = 100010; const ll M = 1e9 + 7; const ll block = 316; const ll mod = 1e9 + 7; const ll P = 263; const ld pi = acos(-1); const ll inf = 9e18; ll add(ll a, ll b) { if(a + b < 0) return a + b + mod; if(a + b >= mod) return a + b - mod; return a + b; } ll sub(ll a, ll b) { return (a - b + mod) % mod; } ll mul(ll a, ll b) { return a * b % mod; } ll binpow(ll a, ll n) { ll res = 1; while(n) { if(n & 1) res = mul(res, a); a = mul(a, a); n >>= 1; } return res; } ll inv(ll x) { return binpow(x, mod - 2); } ll n, m; ll l[N], r[N]; void sub1() { ll ans = 0; for(ll i = 1; i <= n; i++) { ans = max(ans, abs(l[i] - r[i])); } cout << ans << '\n'; } void solve() { cin >> n >> m; multiset<ll> mn, mx; for(ll i = 1; i <= n; i++) cin >> l[i]; for(ll i = 1; i <= m; i++) cin >> r[i]; sort(l + 1, l + n + 1); sort(r + 1, r + m + 1); if(n == m) { sub1(); return; } if(n > m) { for(ll i = 1; i <= m; i++) mn.insert(r[i]); for(ll i = 1; i <= n; i++) mx.insert(l[i]); } else { for(ll i = 1; i <= n; i++) mn.insert(l[i]); for(ll i = 1; i <= m; i++) mx.insert(r[i]); } ll ans = 0; while(!mn.empty()) { ll x = *mn.begin(); auto y = mx.lower_bound(x); if(y == mx.end()) { y--; ans = max(ans, abs(x - *y)); mx.erase(y); } else { ll tmp = abs(x - *y); y--; if(abs(x - *y) < tmp) { tmp = abs(x - *y); mx.erase(y); } else { y++; mx.erase(y); } ans = max(ans, tmp); } mn.erase(mn.begin()); } cout << ans << '\n'; } signed main() { speed; //file; int test = 1; //cin >> test; while(test--) { solve(); } }
#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...