Submission #894412

#TimeUsernameProblemLanguageResultExecution timeMemory
894412vjudge1Cipele (COCI18_cipele)C++17
36 / 90
1060 ms3280 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 = 1e18; 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 sub2() { vector<bool> used(max(n, m) + 1, false); ll ans = 0; bool f = false; if(n > m) f = true; for(ll i = 1; i <= min(n, m); i++) { ll cur = inf; for(ll j = 1; j <= max(n, m); j++) { if(!used[j]) { if(!f && cur > abs(l[i] - r[j])) { cur = abs(l[i] - r[j]); used[j] = true; } else if(f && cur > abs(r[i] - l[j])) { cur = abs(r[i] - l[j]); used[j] = true; } } } ans = max(ans, cur); } 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; } sub2(); // 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...