제출 #1055073

#제출 시각아이디문제언어결과실행 시간메모리
1055073Adomas08Palembang Bridges (APIO15_bridge)C++14
63 / 100
2052 ms7268 KiB
#include <bits/stdc++.h> using namespace std; int k, n; long long curans; vector <int> h; bool sorting(pair <int, int> a, pair <int, int> b){ return a.first + a.second < b.first + b.second; } int findmedian(vector<pair<int, int>> j){ vector <int> d; for (int i = 0; i < j.size(); i++){ d.push_back(j[i].first); d.push_back(j[i].second); } d.erase(remove(d.begin(), d.end(), -1), d.end()); sort (d.begin(), d.end()); if (d.size() == 0) return 0; return (d[d.size() / 2] + d[d.size() / 2 - 1]) / 2; } int main(){ long long ans = 0, dans = 0; int k, n; ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> k >> n; int a[n*2]; vector <int> z; vector <pair<int,int>> v; char b[n], d[n]; for (int i = 0; i < n; i++){ cin >> b[i] >> a[i*2] >> d[i] >> a[i*2+1]; if (b[i] == d[i]){ v.push_back({-1, -1}); z.push_back(-1); z.push_back(-1); } else { dans++; v.push_back({a[i*2], a[i*2+1]}); z.push_back(a[i*2]); z.push_back(a[i*2+1]); } if (a[i*2] > a[i*2+1]){ swap(a[i*2], a[i*2+1]); } dans += a[i*2+1] - a[i*2]; } int f; if (k == 1){ while (k--){ f = findmedian(v); for (int i = 0; i < n; i++){ if (f >= a[i*2] && f <= a[i*2+1]){ v[i].first = -1; v[i].second = -1; } } } for (int i = 0; i < n; i++){ if (b[i] == d[i]){ ans += a[i*2+1] - a[i*2]; } else{ if (v[i].first == -1){ ans += a[i*2+1] - a[i*2] + 1; } else{ if (f < a[i*2]) ans += 1 + a[i*2+1] - a[i*2] + 2 * (a[i*2] - f); if (f > a[i*2+1]) ans += 1 + a[i*2+1] - a[i*2] + 2 * (f - a[i*2+1]); } } } } else{ ans = LLONG_MAX; long long xans; int f, g, c; sort(v.begin(), v.end(), sorting); vector <pair<int, int>>start(v.begin(), v.begin() + 1); vector <pair<int, int>>ends(v.begin() + 1, v.end()); for (int N = 1; N <= n; N++){ h = z; curans = dans; if (N != 1){ start.push_back(v[N-1]); ends.erase(ends.begin()); } f = findmedian(start); g = findmedian(ends); for (int i = 0; i < n; i++){ if ((f >= a[i*2] && f <= a[i*2+1]) || (g >= a[i*2] && g <= a[i*2+1])){ h[i*2] = -1; h[i*2+1] = -1; } } for (int i = 0; i < n; i++){ if (h[i*2] != -1){ if (f < a[i*2]) c = 2 * (a[i*2] - f); else c = 2 * (f - a[i*2+1]); if (g < a[i*2]) c = min(2 * (a[i*2] - g), c); else c = min(2 * (g - a[i*2+1]), c); curans += c; } } ans = min(curans, ans); } } cout << ans; }

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

bridge.cpp: In function 'int findmedian(std::vector<std::pair<int, int> >)':
bridge.cpp:12:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for (int i = 0; i < j.size(); i++){
      |                         ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:77:23: warning: unused variable 'xans' [-Wunused-variable]
   77 |             long long xans;
      |                       ^~~~
#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...