Submission #330973

#TimeUsernameProblemLanguageResultExecution timeMemory
330973ChrisGe123Palembang Bridges (APIO15_bridge)C++14
22 / 100
227 ms15232 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //g++ -std=c++17 -O2 -fsanitize=undefined /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/x86_64-apple-darwin19/bits/stdc++.h #define maxn 100005 #define mod 1000000007 int n, k; pair<ll, pair<ll, ll> > interval[maxn]; ll ans; Tree<pair<ll, int> > endpoints; void setupIO(string s) { ios_base::sync_with_stdio(false); cin.tie(0); freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } int main() { //setupIO("bridges"); ios_base::sync_with_stdio(false); cin.tie(0); cin >> k >> n; int counter = 0; ll pre = 0; endpoints.clear(); for (int i=0; i<n; i++) { char p, q; ll s, t; cin >> p >> s >> q >> t; if (p == q) { pre += abs(s - t); } else { ll l = min(s, t); ll r = max(s, t); interval[counter++] = make_pair(s+t, make_pair(l, r)); pre += r - l + 1; } } n = counter; if (k == 1) { ans = 0; //we just want to find the median of the endpoints for (int i=0; i<n; i++) { endpoints.insert(make_pair(interval[i].second.first, 2*i)); endpoints.insert(make_pair(interval[i].second.second, 2*i+1)); } ll x = (endpoints.find_by_order(n-1)->first + endpoints.find_by_order(n)->first) / 2; cerr << x << endl; for (int i=0; i<n; i++) { ll l = interval[i].second.first; ll r = interval[i].second.second; if (l <= x && x <= r) { continue; } else if (x < l) { ans += 2 * (l-x); } else { ans += 2 * (x-r); } } } else { ans = LLONG_MAX; sort(interval, interval+n); //sorted in order of increasing midpoint for (int i=0; i<n-1; i++) { //things 0 to i take the first bridge, i+1 to n-1 take the second bridge endpoints.clear(); for (int j=0; j<=i; j++) { endpoints.insert(make_pair(interval[j].second.first, 2*j)); endpoints.insert(make_pair(interval[j].second.second, 2*j+1)); } ll x = (endpoints.find_by_order(i)->first + endpoints.find_by_order(i+1)->first) / 2; endpoints.clear(); for (int j=i+1; j<n; j++) { endpoints.insert(make_pair(interval[j].second.first, 2*j)); endpoints.insert(make_pair(interval[j].second.second, 2*j+1)); } ll y = (endpoints.find_by_order(n-i-2)->first + endpoints.find_by_order(n-i-1)->first) / 2; cerr << endl; cerr << i << endl; cerr << x << " " << y << endl; ll temp = 0; for (int j=0; j<=i; j++) { ll l = interval[j].second.first; ll r = interval[j].second.second; if (l <= x && x <= r) { continue; } else if (x < l) { temp += 2 * (l-x); } else { temp += 2 * (x-r); } } //cerr << temp << endl; for (int j=i+1; j<n; j++) { ll l = interval[j].second.first; ll r = interval[j].second.second; if (l <= y && y <= r) { continue; } else if (y < l) { temp += 2 * (l-y); } else { temp += 2 * (y-r); } } cerr << temp << endl; ans = min(ans, temp); } } cout << ans + pre << endl; }

Compilation message (stderr)

bridge.cpp: In function 'void setupIO(std::string)':
bridge.cpp:24:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...