Submission #477280

#	Time	Username	Problem	Language	Result	Execution time	Memory
477280		ymm	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	58 ms	4364 KiB

bridge

///
///   ♪ Let the voice of love take you higher! ♪
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
typedef long long ll;
using namespace std;

ll inf = 1e9+100;
const int N = 100010;
char c1[N], c2[N];
ll a1[N], a2[N];
int k, n;

ll get(int x, int y)
{
	ll ans = 0;
	Loop(i,0,n)
	{
		if(c1[i] == c2[i]) ans += abs(a2[i]-a1[i]);
		else ans += 1+min(abs(a1[i]-x)+abs(a2[i]-x), abs(a1[i]-y)+abs(a2[i]-y));
	}
	return ans;
}

ll bin21i(ll x)
{
	ll l = 0, r = inf;
	while(l < r)
	{
		ll m = (l+r)/2;
		ll v1 = get(x-m,x+m);
		ll v2 = get(x-m-1,x+m+1);
		if(v1 < v2) r = m;
		else        l = m+1;
	}
	return get(x-l,x+l);
}

ll bin21h(ll x)
{
	ll l = 0, r = inf;
	while(l < r)
	{
		ll m = (l+r)/2;
		ll v1 = get(x-m,x+m+1);
		ll v2 = get(x-m-1,x+m+2);
		if(v1 < v2) r = m;
		else        l = m+1;
	}
	return get(x-l,x+l+1);
}

ll bin21(ll x){return (x&1)?bin21h(x/2):bin21i(x/2);}

ll bin22()
{
	ll l = 2*inf, r = 0;
	Loop(i,0,n)
	{
		if(c1[i] != c2[i])
			l = min(l, a1[i]+a2[i]),
			r = max(r, a1[i]+a2[i]);
	}
	while(l < r)
	{
		ll m = (l+r)/2;
		ll v1 = bin21(m);
		ll v2 = bin21(m+1);
		if(v1 < v2) r = m;
		else        l = m+1;
	}
	return bin21(l);
}

ll bin11()
{
	ll l = 0, r = inf;
	while(l < r)
	{
		ll m = (l+r)/2;
		ll v1 = get(m,-inf);
		ll v2 = get(m+1,-inf);
		if(v1 < v2) r = m;
		else        l = m+1;
	}
	return get(l,-inf);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	#ifndef EVAL
	freopen("in.txt", "r", stdin);
	#endif
	cin >> k >> n;
	Loop(i,0,n)
	{
		cin >> c1[i] >> a1[i];
		cin >> c2[i] >> a2[i];
	}
	cout << (k==2?bin22():bin11()) << '\n';
}

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