제출 #119555

#제출 시각아이디문제언어결과실행 시간메모리
119555Charis02Palembang Bridges (APIO15_bridge)C++14
22 / 100
215 ms16128 KiB
#include<iostream> #include<stdio.h> #include<vector> #include<cmath> #include<queue> #include<utility> #include<string.h> #include<map> #include<set> #include<algorithm> #define ll long long #define pi pair < ll,ll > #define mp(a,b) make_pair(a,b) #define rep(i,a,b) for(int i = a;i < b;i++) #define N 100004 #define INF 1e18 using namespace std; ll n,k; pi ar[N]; ll b,d; char a,c; ll ans,cnt; vector <ll>possible; vector < ll > ola; set < ll > p; ll abso(ll x) { if(x<0) return -x; return x; } ll checkbridge(ll x,ll y) { ll res = ans; rep(i,0,cnt) { if(ar[i].first <= x && x <= ar[i].second) { res += ar[i].second-ar[i].first; } else if(ar[i].first <= y && y <= ar[i].second) { res+=ar[i].second-ar[i].first; } else { res += 2*min(min(abso(ar[i].first-x),abso(ar[i].second-x)),min(abso(ar[i].first-y),abso(ar[i].second-y)))+(ar[i].second-ar[i].first); } } // cout << x << " " << y << " " << res << endl; return res; } ll findans(ll x) { ll low = x; ll high = possible.size()-1; ll res = x; while(low <= high) { ll mid = (low+high)/2; if(checkbridge(possible[x],possible[mid-1]) >= checkbridge(possible[x],possible[mid])) { low = mid+1; res = mid; } else { high = mid-1; } } ll fin = checkbridge(possible[x],possible[res]); low = 0; high = x; res = 0; while(low <= high) { ll mid = (low+high)/2; if(checkbridge(possible[x],possible[mid-1]) >= checkbridge(possible[x],possible[mid])) { low = mid+1; res = mid; } else { high = mid-1; } } return min(fin,checkbridge(possible[x],possible[res])); } void solve2() { ll fin = checkbridge(possible[0],possible[0]); rep(i,0,possible.size()) { if(fin < findans(i)) break; else fin = findans(i); } cout << fin << endl; return; } int main() { ios_base::sync_with_stdio(false); //freopen("bridge_3_3.in","r",stdin); cin >> k >> n; rep(i,0,n) { cin >> a >> b >> c >> d; if(d < b) swap(b,d); if(a == c) ans += d-b; else { ar[cnt].first = b; ar[cnt].second = d; ola.push_back(b); ola.push_back(d); ans++; cnt++; } } if(cnt == 0) { cout << ans; return 0; } rep(i,0,cnt) { p.insert(ar[i].first); p.insert(ar[i].second); } for(set < ll >::iterator it = p.begin();it != p.end();it++) { possible.push_back(*it); } if(k == 2) { solve2(); return 0; } ll low = 0; ll high = possible.size()-1; ll res = 0; while(low <= high) { ll mid = (low+high)/2; if(checkbridge(possible[mid-1],possible[mid-1]) >= checkbridge(possible[mid],possible[mid])) { low = mid+1; res = mid; } else { high = mid-1; } } cout << checkbridge(possible[res],possible[res]); return 0; } /* 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 2 3 A 1 B 1 A 4 B 7 A 10 B 12 */

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

bridge.cpp: In function 'void solve2()':
bridge.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
bridge.cpp:110:9:
     rep(i,0,possible.size())
         ~~~~~~~~~~~~~~~~~~~         
bridge.cpp:110:5: note: in expansion of macro 'rep'
     rep(i,0,possible.size())
     ^~~
#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...