Submission #1064120

#TimeUsernameProblemLanguageResultExecution timeMemory
1064120TheQuantiXWiring (IOI17_wiring)C++17
0 / 100
239 ms31160 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll INF = 1000000000000000000LL; ll n, m, q, k, x, y, a, c; long long min_total_length(std::vector<int> r, std::vector<int> b) { n = r.size(); m = b.size(); vector< pair<ll, ll> > vec; for (int i : r) { vec.push_back({i, 1}); } for (int i : b) { vec.push_back({i, 2}); } sort(vec.begin(), vec.end()); set<ll> st; for (int i = 0; i < n + m; i++) { if (i != 0 && vec[i].second != vec[i - 1].second) { st.insert(vec[i].first); } if (i != n + m - 1 && vec[i].second != vec[i + 1].second) { st.insert(vec[i].first); } } set< pair<ll, pair<ll, ll> > > two, one; vector<bool> used1(n), used2(m); for (int i = 0; i < n; i++) { if (st.count(r[i])) { continue; } if (r[i] <= b[b.size() - 1]) { ll x = lower_bound(b.begin(), b.end(), r[i]) - b.begin(); two.insert({abs(r[i] - b[x]), {i, x}}); } if (r[i] >= b[0]) { ll x = (--upper_bound(b.begin(), b.end(), r[i])) - b.begin(); two.insert({abs(r[i] - b[x]), {i, x}}); } } for (int i = 0; i < m; i++) { if (st.count(b[i])) { continue; } if (b[i] <= r[r.size() - 1]) { ll x = lower_bound(r.begin(), r.end(), b[i]) - r.begin(); two.insert({abs(r[x] - b[i]), {x, i}}); } if (b[i] >= r[0]) { ll x = (--upper_bound(r.begin(), r.end(), b[i])) - r.begin(); two.insert({abs(r[x] - b[i]), {x, i}}); } } // for (auto i : two) { // cout << i.first << ' ' << i.second.first << ' ' << i.second.second << '\n'; // } // cout << '\n'; ll ans = 0; while (two.size() > 0 || one.size() > 0) { pair<ll, ll> p1 = {-1, -1}, p2 = {-1, -1}; while (!two.empty() && p2.first == -1) { p2 = (*two.begin()).second; two.erase({abs(r[p2.first] - b[p2.second]), p2}); if (used1[p2.first] && used2[p2.second]) { p2 = {-1, -1}; continue; } if (used1[p2.first] || used2[p2.second]) { one.insert({abs(r[p2.first] - b[p2.second]), p2}); p2 = {-1, -1}; continue; } break; } while (!one.empty() && p1.first == -1) { p1 = (*one.begin()).second; one.erase({abs(r[p1.first] - b[p1.second]), p1}); if (used1[p1.first] && used2[p1.second]) { p1 = {-1, -1}; continue; } break; } if (p1.first == -1 && p2.first == -1) { break; } ll a1 = (p1.first == -1 ? INF : abs(r[p1.first] - b[p1.second])); a1 *= 2; ll a2 = (p2.first == -1 ? INF : abs(r[p2.first] - b[p2.second])); if (a2 < a1) { ans += a2; used1[p2.first] = 1; used2[p2.second] = 1; } else { ans += a1 / 2; used1[p1.first] = 1; used2[p1.second] = 1; } } // for (int i = 0; i < n; i++) { // cout << used1[i] << ' '; // } // cout << '\n'; // for (int i = 0; i < m; i++) { // cout << used2[i] << ' '; // } // cout << '\n'; for (int i = 0; i < n; i++) { if (r[i] <= b[b.size() - 1]) { ll x = lower_bound(b.begin(), b.end(), r[i]) - b.begin(); if (!used1[i] && !used2[x]) { two.insert({abs(r[i] - b[x]), {i, x}}); } else if (!used1[i] || !used2[x]) { one.insert({abs(r[i] - b[x]), {i, x}}); } } if (r[i] >= b[0]) { ll x = (--upper_bound(b.begin(), b.end(), r[i])) - b.begin(); if (!used1[i] && !used2[x]) { two.insert({abs(r[i] - b[x]), {i, x}}); } else if (!used1[i] || !used2[x]) { one.insert({abs(r[i] - b[x]), {i, x}}); } } } for (int i = 0; i < m; i++) { if (b[i] <= r[r.size() - 1]) { ll x = lower_bound(r.begin(), r.end(), b[i]) - r.begin(); if (!used1[x] && !used2[i]) { two.insert({abs(r[x] - b[i]), {x, i}}); } else if (!used1[x] || !used2[i]) { one.insert({abs(r[x] - b[i]), {x, i}}); } } if (b[i] >= r[0]) { ll x = (--upper_bound(r.begin(), r.end(), b[i])) - r.begin(); if (!used1[x] && !used2[i]) { two.insert({abs(r[x] - b[i]), {x, i}}); } else if (!used1[x] || !used2[i]) { one.insert({abs(r[x] - b[i]), {x, i}}); } } } // for (auto i : two) { // cout << i.first << ' ' << i.second.first << ' ' << i.second.second << '\n'; // } // cout << '\n'; while (two.size() > 0 || one.size() > 0) { // for (int i = 0; i < n; i++) { // cout << used1[i] << ' '; // } // cout << '\n'; // for (int i = 0; i < m; i++) { // cout << used2[i] << ' '; // } // cout << '\n'; // cout << '\n'; pair<ll, ll> p1 = {-1, -1}, p2 = {-1, -1}; while (!two.empty() && p2.first == -1) { p2 = (*two.begin()).second; two.erase({abs(r[p2.first] - b[p2.second]), p2}); if (used1[p2.first] && used2[p2.second]) { p2 = {-1, -1}; continue; } if (used1[p2.first] || used2[p2.second]) { one.insert({abs(r[p2.first] - b[p2.second]), p2}); p2 = {-1, -1}; continue; } break; } while (!one.empty() && p1.first == -1) { p1 = (*one.begin()).second; one.erase({abs(r[p1.first] - b[p1.second]), p1}); if (used1[p1.first] && used2[p1.second]) { p1 = {-1, -1}; continue; } break; } if (p1.first == -1 && p2.first == -1) { break; } // cout << p1.first << ' ' << p1.second << '\n'; // cout << p2.first << ' ' << p2.second << '\n'; // cout << '\n'; ll a1 = (p1.first == -1 ? INF : abs(r[p1.first] - b[p1.second])); a1 *= 2; ll a2 = (p2.first == -1 ? INF : abs(r[p2.first] - b[p2.second])); if (a2 < a1) { ans += a2; used1[p2.first] = 1; used2[p2.second] = 1; } else { ans += a1 / 2; used1[p1.first] = 1; used2[p1.second] = 1; } } return ans; }
#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...