Submission #60591

#	Time	Username	Problem	Language	Result	Execution time	Memory
60591		Eae02	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	4 ms	604 KiB

bridge

#include <bits/stdc++.h>

int main()
{
	int numBridges, numPeople;
	std::cin >> numBridges;
	std::cin >> numPeople;
	
	if (numBridges != 1)
		return 1;
	
	uint64_t baseDistSum = 0;
	std::vector<std::pair<int, int>> cPeople;
	cPeople.reserve(numPeople);
	
	for (int i = 0; i < numPeople; i++)
	{
		char z1, z2;
		int p1, p2;
		
		std::cin >> z1;
		std::cin >> p1;
		std::cin >> z2;
		std::cin >> p2;
		
		if (p1 > p2)
			std::swap(p1, p2);
		
		baseDistSum += p2 - p1;
		
		if (z1 != z2)
		{
			cPeople.emplace_back(p1, p2);
		}
	}
	
	const int MAX_BEG = 1000000001;
	
	auto MinExtDist = [&] (uint64_t pos) -> uint64_t
	{
		uint64_t dist = 0;
		for (const auto& p : cPeople)
		{
			if (pos <= p.first)
				dist += (p.first - pos) * 2 + 1; 
			else if (pos >= p.second)
				dist += (pos - p.second) * 2 + 1;
			else
				dist += 1;
		}
		return dist;
	};
	
	#ifdef LOCAL
	for (int i = 0; i < 20; i++)
	{
		std::cout << " " << (baseDistSum + MinExtDist(i));
	}
	std::cout << std::endl;
	#endif
	
	int x;
	
	uint64_t min = 0;
	uint64_t max = MAX_BEG + 1;
	while (true)
	{
		uint64_t mid = min + (max - min) / 2;
		uint64_t dm = MinExtDist(mid);
		
		#ifdef LOCAL
		std::cout << min << ", " << max << ", " << mid << " : " << dm << std::endl;
		#endif
		
		if (mid >= MAX_BEG || dm <= MinExtDist(mid + 1))
		{
			if (mid == 0 || dm <= MinExtDist(mid - 1))
			{
				x = dm;
				break;
			}
			
			max = mid;
		}
		else
		{
			if (mid != 0 && dm <= MinExtDist(mid - 1))
			{
				x = dm;
				break;
			}
			min = mid + 1;
		}
	}
	
	std::cout << baseDistSum + x << std::endl;
}

Compilation message (stderr)

bridge.cpp: In lambda function:
bridge.cpp:44:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pos <= p.first)
        ~~~~^~~~~~~~~~
bridge.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if (pos >= p.second)
             ~~~~^~~~~~~~~~~

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