제출 #60617

#제출 시각아이디문제언어결과실행 시간메모리
60617Eae02Palembang Bridges (APIO15_bridge)C++14
0 / 100
5 ms576 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); 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; }

컴파일 시 표준 에러 (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]);
                 ~~~~~~~~^~~~~~
#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...