This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |