Submission #60564

#	Time	Username	Problem	Language	Result	Execution time	Memory
60564		Eae02	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	2070 ms	504 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);
		}
	}
	
	auto MinExtDist = [&] (int pos)
	{
		int 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;
	};
	
	int x;
	
	int min = 0;
	int max = 1000000001;
	while (true)
	{
		int mid = min + (max - min) / 2;
		int dm = MinExtDist(mid);
		int dr = MinExtDist(mid + 1);
		
		//std::cout << min << ", " << max << std::endl;
		
		if (dm >= dr)
		{
			int dl = MinExtDist(mid - 1);
			if (dm >= dm)
			{
				x = dm;
				break;
			}
			
			min = mid;
		}
		else
		{
			max = mid + 1;
		}
	}
	
	std::cout << baseDistSum + x << std::endl;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:67:11: warning: self-comparison always evaluates to true [-Wtautological-compare]
    if (dm >= dm)
        ~~~^~~~~
bridge.cpp:66:8: warning: unused variable 'dl' [-Wunused-variable]
    int dl = MinExtDist(mid - 1);
        ^~

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