이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <vector>
const int N = 1000000000;
int k, n;
std::vector<std::pair<int, int> > a;
long long test2(int x, int y)
{
long long s = 0;
for (int i = 0; i < (int)a.size(); ++i) s += std::min(std::max(a[i].first - x, 0) + std::max(x - a[i].second, 0), std::max(a[i].first - y, 0) + std::max(y - a[i].second, 0));
return s;
}
long long test1(int x)
{
int l = x, r = N, opt;
while (l <= r) {
int m = l + r >> 1;
if (test2(x, m) <= test2(x, m + 1)) {
opt = m;
r = m - 1;
}
else l = m + 1;
}
return test2(x, opt);
}
long long test0()
{
int l = 0, r = N, opt;
while (l <= r) {
int m = l + r >> 1;
if (test1(m) <= test1(m + 1)) {
opt = m;
r = m - 1;
}
else l = m + 1;
}
return test1(opt);
}
long long test(int x)
{
long long r = ~((long long)1 << 63);
for (int i = 0; i < (int)a.size(); ++i) {
r = std::min(r, test2(x, a[i].first));
r = std::min(r, test2(x, a[i].first - 1));
r = std::min(r, test2(x, a[i].first + 1));
r = std::min(r, test2(x, a[i].second));
r = std::min(r, test2(x, a[i].second - 1));
r = std::min(r, test2(x, a[i].second + 1));
}
return r;
}
int main()
{
long long ans = 0;
scanf("%d%d", &k, &n);
for (int i = 0; i < n; ++i) {
char type_from, type_to;
int from, to;
scanf(" %c%d %c%d", &type_from, &from, &type_to, &to);
if (from > to) std::swap(from, to);
ans += to - from;
if (type_from != type_to) {
a.push_back(std::make_pair(from, to));
++ans;
}
}
long long mn = ~((long long)1 << 63);
for (int i = 0; i < 100; ++i) mn = std::min(mn, test2(-N, i));
printf("%lld\n", ans + mn * 2);
return 0;
if (k == 1) printf("%lld\n", ans + test1(-N) * 2);
else {
long long r = ~((long long)1 << 63);
for (int i = 0; i < (int)a.size(); ++i) {
r = std::min(r, test(a[i].first));
r = std::min(r, test(a[i].second));
}
printf("%lld\n", ans + r * 2);
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bridge.cpp: In function 'long long int test1(int)':
bridge.cpp:20:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
20 | int m = l + r >> 1;
| ~~^~~
bridge.cpp: In function 'long long int test0()':
bridge.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int m = l + r >> 1;
| ~~^~~
bridge.cpp: In function 'int main()':
bridge.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d%d", &k, &n);
| ~~~~~^~~~~~~~~~~~~~~~
bridge.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf(" %c%d %c%d", &type_from, &from, &type_to, &to);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'long long int test1(int)':
bridge.cpp:27:14: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
27 | return test2(x, opt);
| ~~~~~^~~~~~~~
bridge.cpp: In function 'long long int test0()':
bridge.cpp:41:14: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
41 | return test1(opt);
| ~~~~~^~~~~
# | 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... |