Submission #602969

#	Time	Username	Problem	Language	Result	Execution time	Memory
602969		Fidan	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	212 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=(1e18)+10;
int main(){
	ll k, n;
	cin>>k>>n;
	if(k==1){
		ll sum=0, i;
		vector<pair<ll, ll>> v;
		vector<ll> v1, v2;
		for(i=0; i<n; i++){
			char c1, c2;
			ll i1, i2;
			cin>>c1>>i1>>c2>>i2;
			sum+=abs(i1-i2);
			if(c1!=c2){
				if(i2<i1){
					swap(i1, i2);
				}
				sum++;
				v.push_back({i1, i2});
			}
		}
		
		k=v.size();
		ll lo=0, hi=(1e9);
		ll cvb;
		
		while(lo<hi){
			ll mid=(lo+hi)/2;
			ll l=0, r=0;
			for(auto p: v){
				ll a1=p.first, a2=p.second;
				if(a1>mid) l++;
				if(a2<mid) r++;
			}
			cvb=mid;
			if(l>r){
				lo=mid+1;
			}
			else if(l<r){
				hi=mid-1;
			}
			else{
				break;
			}
		}
		
		for(auto p: v){
			ll a1=p.first, a2=p.second;
			if(min(a1, a2)>cvb) sum+=2*(min(a1, a2)-cvb);
			else if(max(a1, a2)<cvb) sum+=2*(cvb-max(a1, a2));
		}
		cout<<sum;
	}
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37