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>
using namespace std;
const long long int INF = 1e18;
long long int K, N;
long long int build1, build2;
char zone1, zone2;
long long int Dmin = 0;
struct Place {
char zone;
long long int building;
};
vector<pair<Place, Place> > people;
long long int cost(long long int currK) {
long long int currMin = 0;
for (int j = 0; j < people.size(); j++) {
currMin += abs(people[j].first.building - currK);
currMin++;
currMin += abs(people[j].second.building - currK);
}
return currMin;
}
const bool cmp(const pair<Place, Place> &a, pair<Place, Place> &b) {
return a.first.building < b.first.building;
}
const bool cmp2(const pair<Place, Place> &a, pair<Place, Place> &b) {
return a.second.building < b.second.building;
}
int main() {
cin >> K >> N;
for (int i = 0; i < N; i++) {
cin >> zone1 >> build1 >> zone2 >> build2;
if (zone1 == zone2) {
Dmin += abs(build2 - build1);
} else {
if (zone1 == 'B') {
swap(zone1, zone2);
swap(build1, build2);
}
if (zone1 == 'B') {
swap(zone1, zone2);
swap(build1, build2);
}
people.push_back(make_pair(
(Place){zone1, build1},
(Place){zone2, build2}
));
}
}
int M = people.size();
// cout << M << "\n";
long long int possibleMin = INF;
if (M == 0) possibleMin = 0;
else {
sort(people.begin(), people.end(), cmp);
for (int i = M/2; i <= M/2 + 1; i++) {
possibleMin = min(possibleMin, cost(people[i].first.building));
possibleMin = min(possibleMin, cost(people[i].second.building));
}
sort(people.begin(), people.end(), cmp2);
for (int i = M/2; i <= M/2 + 1; i++) {
possibleMin = min(possibleMin, cost(people[i].first.building));
possibleMin = min(possibleMin, cost(people[i].second.building));
}
}
cout << possibleMin + Dmin << "\n";
}
Compilation message (stderr)
bridge.cpp: In function 'long long int cost(long long int)':
bridge.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<Place, Place> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int j = 0; j < people.size(); j++) {
| ~~^~~~~~~~~~~~~~~
# | 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... |