Submission #453471

#	Time	Username	Problem	Language	Result	Execution time	Memory
453471		nonsensenonsense1	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	161 ms	2052 KiB

bridge

#include <cstdio>
#include <vector>

const int N = 1000000000;

int k, n;
std::vector<std::pair<int, int> > a;

long long test2(int x, int y) 
{
	long long s = 0;
	for (int i = 0; i < (int)a.size(); ++i) s += std::min(std::max(a[i].first - x, 0) + std::max(x - a[i].second, 0), std::max(a[i].first - y, 0) + std::max(y - a[i].second, 0));
	return s;
}

long long test1(int x) 
{
	int l = x, r = N, opt;
	while (l <= r) {
		int m = l + r >> 1;
		if (test2(x, m) <= test2(x, m + 1)) {
			opt = m;
			r = m - 1;
		}
		else l = m + 1;
	}
	return test2(x, opt);
}

long long test0() 
{
	int l = 0, r = N, opt;
	while (l <= r) {
		int m = l + r >> 1;
		if (test1(m) <= test1(m + 1)) {
			opt = m;
			r = m - 1;
		}
		else l = m + 1;
	}
	return test1(opt);
}

int main() 
{
	long long ans = 0;
	scanf("%d%d", &k, &n);
	for (int i = 0; i < n; ++i) {
		char type_from, type_to;
		int from, to;
		scanf(" %c%d %c%d", &type_from, &from, &type_to, &to);
		if (from > to) std::swap(from, to);
		ans += to - from;
		if (type_from != type_to) {
			a.push_back(std::make_pair(from, to));
			++ans;
		}
	}
	if (k == 1) printf("%lld\n", ans + test1(-N) * 2);
	else {
		long long r = ((long long)1 << 63);
		for (int i = 0; i < (int)a.size(); ++i) {
			r = std::min(r, test1(a[i].first));
			r = std::min(r, test1(a[i].second));
		}
		printf("%lld\n", ans + r * 2);
	}
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'long long int test1(int)':
bridge.cpp:20:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |   int m = l + r >> 1;
      |           ~~^~~
bridge.cpp: In function 'long long int test0()':
bridge.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int m = l + r >> 1;
      |           ~~^~~
bridge.cpp: In function 'int main()':
bridge.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d", &k, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridge.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf(" %c%d %c%d", &type_from, &from, &type_to, &to);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'long long int test1(int)':
bridge.cpp:27:14: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |  return test2(x, opt);
      |         ~~~~~^~~~~~~~
bridge.cpp: In function 'long long int test0()':
bridge.cpp:41:14: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |  return test1(opt);
      |         ~~~~~^~~~~

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