제출 #653446

#제출 시각아이디문제언어결과실행 시간메모리
653446ayallaPalembang Bridges (APIO15_bridge)C++14
63 / 100
2071 ms29304 KiB
#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 int long long int #define endl '\n' #define pb push_back #define pi pair<int, int> #define pii pair<int, pi> #define fir first #define sec second #define MAXN 200005 #define mod 998244353 int calc(vector<int> &v, int x) { int ans = 0; for (auto const &i : v) ans += abs(i - x); return ans; } int solve(vector<int> &v) { ordered_set<pi> s; map<int, int> mp; for (auto const &i : v) { s.insert({i, mp[i]}); mp[i]++; } int sz = v.size(); int x = (*s.find_by_order(sz / 2)).fir; int ans = calc(v, x); if (v.size() > 1) { int x = (*s.find_by_order((sz / 2) - 1)).fir; ans = min(ans, calc(v, x)); } return ans; } void solve1(int n, int k) { int ans = 0; vector<int> pts; for (int i = 0; i < n; i++) { char c1, c2; int a, b; cin >> c1 >> a >> c2 >> b; if (c1 == c2) { ans += abs(a - b); } else { ans++; pts.pb(a); pts.pb(b); } } if (!pts.size()) { cout << ans << endl; return; } sort(pts.begin(), pts.end()); ans += solve(pts); cout << ans << endl; } void solve2(int n, int k) { vector<pi> aux; vector<pi> v; int ans = 0; for (int i = 0; i < n; i++) { char c1, c2; int a, b; cin >> c1 >> a >> c2 >> b; v.pb({a, b}); if (c1 == c2) { ans += abs(a - b); } else { ans++; aux.pb({a + b, i}); } } if (!aux.size()) { cout << ans << endl; return; } sort(aux.begin(), aux.end()); vector<int> pts; for (auto const &i : aux) { pts.pb(v[i.sec].fir); pts.pb(v[i.sec].sec); } int need = ans; vector<int> pts2; ans += solve(pts); while (pts.size() > 2) { pts2.pb(pts.back()); pts.pop_back(); pts2.pb(pts.back()); pts.pop_back(); int curr = need + solve(pts) + solve(pts2); ans = min(ans, curr); } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> k >> n; if (k == 1) solve1(n, k); else solve2(n, k); return 0; }
#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...