oj.uz

Submission #60606

# Submission time Handle Problem Language Result Execution time Memory
60606 2018-07-24T11:32:22 Z Eae02 Palembang Bridges (APIO15_bridge) C++14
8 / 100
 2000 ms 1388 KB 
#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);
	
	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);
		}
	}
	
	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;
	
	uint64_t min = minPos;
	uint64_t max = maxPos + 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 >= maxPos || 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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 7 ms 392 KB Output is correct
4 Correct 13 ms 392 KB Output is correct
5 Correct 14 ms 392 KB Output is correct
6 Correct 6 ms 392 KB Output is correct
7 Correct 7 ms 392 KB Output is correct
8 Correct 5 ms 392 KB Output is correct
9 Correct 12 ms 472 KB Output is correct
10 Correct 10 ms 472 KB Output is correct
11 Correct 11 ms 544 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 560 KB Output is correct
2 Correct 3 ms 560 KB Output is correct
3 Correct 8 ms 560 KB Output is correct
4 Correct 13 ms 560 KB Output is correct
5 Correct 12 ms 560 KB Output is correct
6 Correct 8 ms 560 KB Output is correct
7 Correct 7 ms 560 KB Output is correct
8 Correct 8 ms 560 KB Output is correct
9 Correct 13 ms 620 KB Output is correct
10 Correct 10 ms 620 KB Output is correct
11 Correct 11 ms 624 KB Output is correct
12 Execution timed out 2041 ms 1388 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1388 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1388 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1388 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -