Submission #60601

#TimeUsernameProblemLanguageResultExecution timeMemory
60601Eae02Palembang Bridges (APIO15_bridge)C++14
0 / 100
3 ms520 KiB
#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 = 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 (stderr)

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)
             ~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...