Submission #60617

#	Time	Username	Problem	Language	Result	Execution time	Memory
60617		Eae02	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	5 ms	576 KiB

bridge

#include <bits/stdc++.h>

int main()
{
	int numBridges, numPeople;
	std::cin >> numBridges;
	std::cin >> numPeople;
	
	if (numBridges != 1)
		return 1;
	
	int minPos = INT32_MAX;
	int maxPos = 0;
	
	uint64_t baseDistSum = 0;
	std::vector<std::pair<int, int>> cPeople;
	cPeople.reserve(numPeople);
	
	std::vector<int> points;
	
	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;
		
		minPos = std::min(p1, minPos);
		minPos = std::min(p2, minPos);
		maxPos = std::max(p1, maxPos);
		maxPos = std::max(p2, maxPos);
		
		if (p1 > p2)
			std::swap(p1, p2);
		
		baseDistSum += p2 - p1;
		
		if (z1 != z2)
		{
			cPeople.emplace_back(p1, p2);
			points.push_back(p1);
			if (p1 != p2)
				points.push_back(p2);
		}
	}
	
	std::sort(points.begin(), points.end());
	
	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
	/*
	uint64_t x = cPeople.empty() ? 0 : UINT64_MAX;
	for (const auto& p : cPeople)
	{
		x = std::min(x, MinExtDist(p.first));
		x = std::min(x, MinExtDist(p.second));
	}
	*/
	
	int x = 0;
	int min = 0;
	int max = points.size();
	while (min < max)
	{
		uint64_t mid = min + (max - min) / 2;
		
		uint64_t dl = mid <= min ? UINT64_MAX : MinExtDist(points[mid - 1]);
		uint64_t dr = mid + 1 >= max ? UINT64_MAX : MinExtDist(points[mid + 1]);
		uint64_t dm = MinExtDist(points[mid]);
		
		if (dm <= dr && dm <= dl)
		{
			x = dm;
			break;
		}
		
		if (dl <= dm)
		{
			max = mid;
		}
		else
		{
			min = mid + 1;
		}
	}
	
	/*
	int x;
	
	uint64_t min = minPos;
	uint64_t max = maxPos + 1;
	while (true)
	{
		uint64_t mid = min + (max - min) / 2;
		
		uint64_t dl = mid <= min ? UINT64_MAX : MinExtDist(mid - 1);
		uint64_t dr = mid + 1 >= max ? UINT64_MAX : MinExtDist(mid + 1);
		uint64_t dm = MinExtDist(mid);
		
		if (dm <= dr && dm <= dl)
		{
			x = dm;
			break;
		}
		
		if (dl <= dm)
		{
			max = mid;
		}
		else
		{
			min = mid + 1;
		}
	}*/
	
	std::cout << baseDistSum + x << std::endl;
}

Compilation message (stderr)

bridge.cpp: In lambda function:
bridge.cpp:57:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pos <= p.first)
        ~~~~^~~~~~~~~~
bridge.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if (pos >= p.second)
             ~~~~^~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   uint64_t dl = mid <= min ? UINT64_MAX : MinExtDist(points[mid - 1]);
                 ~~~~^~~~~~
bridge.cpp:91:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   uint64_t dr = mid + 1 >= max ? UINT64_MAX : MinExtDist(points[mid + 1]);
                 ~~~~~~~~^~~~~~

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