제출 #558979

#제출 시각아이디문제언어결과실행 시간메모리
558979hhhhauraPalembang Bridges (APIO15_bridge)C++14
100 / 100
274 ms15168 KiB
#define wiwihorz #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("sse") #pragma loop-opt(on) #define rep(i, a, b) for(int i = a; i <= b; i ++) #define rrep(i, a, b) for(int i = b; i >= a; i --) #define all(x) x.begin(), x.end() #define ceil(a, b) ((a + b - 1) / (b)) #define int long long int #define lld long double #define pii pair<int, int> #define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()) #define INF 1000000000000000000 #define MOD 1000000007 #define eps (1e-9) using namespace std; #ifdef wiwihorz #define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a) void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; } void kout() { cerr << endl; } template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);} #else #define print(...) 0 #define vprint(...) 0 #endif #define x first #define y second namespace solver1 { int n, k, ans; vector<pii> v; vector<int> a; void init_(int _n, int _k) { ans = 0; n = _n, k = _k; assert(k == 1); v.clear(); } void solve() { n = signed(v.size()); rep(i, 0, n - 1) { a.push_back(v[i].x); a.push_back(v[i].y); } sort(all(a)); int mid = a[(n * 2 - 1) / 2]; for(auto i : a) ans += abs(mid - i); cout << ans + n << "\n"; } }; namespace solver2 { int n, k, ans, sa, sb; vector<pii> v; vector<int> L, R; multiset<int> a, b; void init_(int _n, int _k) { ans = 0, sa = 0, sb = 0; n = _n, k = _k; assert(k == 2); } void insert(int x) { if(!a.size()) { a.insert(x); sa += x; } else { if(x <= *a.rbegin()) { a.insert(x); sa += x; } else { b.insert(x); sb += x; } if(a.size() > b.size() + 1) { auto it = prev(a.end()); sa -= *it, sb += *it; b.insert(*it); a.erase(it); } if(b.size() > a.size()) { auto it = b.begin(); sb -= *it, sa += *it; a.insert(*it); b.erase(it); } } } void solve() { n = v.size(); L.assign(n, 0); R.assign(n, 0); sa = 0, sb = 0; sort(all(v), [&](pii a, pii b){ return a.x + a.y < b.x + b.y; }); rep(i, 0, n - 1) { insert(v[i].x); insert(v[i].y); L[i] = sb - sa; } sa = 0, sb = 0; a.clear(); b.clear(); rrep(i, 0, n - 1) { insert(v[i].x); insert(v[i].y); R[i] = sb - sa; } int best = INF; rep(i, 0, n) { int val = 0; if(i - 1 >= 0) val += L[i - 1]; if(i < n) val += R[i]; best = min(best, val); } cout << ans + best + n << "\n"; } }; signed main() { ios::sync_with_stdio(false), cin.tie(0); int k, n; cin >> k >> n; if(k == 1) { using namespace solver1; init_(n, k); rep(i, 1, n) { char x, y; int a, b; cin >> x >> a; cin >> y >> b; if(x == y) ans += abs(a - b); else v.push_back({a, b}); } solve(); } else { using namespace solver2; init_(n, k); rep(i, 1, n) { char x, y; int a, b; cin >> x >> a; cin >> y >> b; if(x == y) ans += abs(a - b); else v.push_back({a, b}); } solve(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
bridge.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
bridge.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~
#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...