Submission #921941

#	Time	Username	Problem	Language	Result	Execution time	Memory
921941		belgianbot	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	91 ms	7864 KiB

bridge

#include <bits/stdc++.h>
#define int long long
#define sz(x) (long long)(x.size())

using namespace std;

struct traj{
	int l, r;
	long double mid;
};
vector <traj> a;

int score(int mid) {
	int ans(0);
	vector<int> b;
	int i(0);
	for (;i < sz(a) && a[i].mid <= mid ; i++){
		b.push_back(a[i].l);
		b.push_back(a[i].r);
	}
	sort (b.begin(), b.end());
	int b1 = b[sz(b) / 2];
	b.clear();
	int b2 = 0;
	if (i != sz(a)) {
		for (;i < sz(a); i++) {
			b.push_back(a[i].l);
			b.push_back(a[i].r);
		}
		sort(b.begin(), b.end());
		b2 = b[sz(b) / 2];
	}
	
 	i = 0;
	for (;i < sz(a) && a[i].mid <= mid; i++) {
		ans += abs(a[i].l - b1);
		ans += abs(a[i].r - b1);
	}
	for (;i < sz(a); i++) {
		ans += abs(a[i].l - b2);
		ans += abs(a[i].r - b2);
	}
	return ans;
}

int trinary_search(int l, int r){
	
	if (r - l <= 10) {
		int ans(LLONG_MAX);
		for (int i(l); i <= r; i++)
			ans = min(ans, score(a[i].mid));
		return ans;
	}
	int mid1 = a[l + (r - l) / 3].mid;
	int mid2 = a[l + 2 * (r - l) / 3].mid;
	
	if (score(mid1) <= score(mid2))
		return trinary_search(l, l + 2 * (r - l) / 3);
	return trinary_search(l + (r - l) / 3 + 1, r);
}
signed main(){
	int K, N; cin >> K >> N;
	
	int ans(0);
	for (int i(0); i < N; i++) {
		char riv1, riv2;
		int pos1, pos2;
		cin >> riv1 >> pos1 >> riv2 >> pos2;
		
		if (pos2 < pos1) swap(pos1, pos2);
		if (riv1 != riv2) {
			ans++;
			a.push_back ({pos1, pos2, (long double)( (pos1 + pos2) / 2)});
		}
		else ans += pos2 - pos1;
	}
	if (sz(a) == 0){
		 cout << ans << '\n';
		 return 0;
	 }
	sort (a.begin(), a.end(), [](traj &A, traj &B){return A.mid < B.mid;});
	
	if (K == 1) cout << ans + score(LLONG_MAX) << '\n';
	else cout << ans + trinary_search(0, sz(a) - 1) << '\n';
		
	return 0;
}

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