| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1054190 | kiryl_krutsko | Palembang Bridges (APIO15_bridge) | C++14 | 0 ms | 0 KiB |
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 <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct way {
int left, right;
way(int n1, int n2) {
left = min(n1, n2);
right = max(n1, n2);
}
};
int bs(int start, int end, vector<way>* vec, int start_ans) {
int ans = start_ans;
int right = 0;
int left = 0;
int mid = (start + end) / 2;
//cout << mid << " : ";
for (int i = 0; i < vec->size();i++) {
way cur = vec->at(i);
if (cur.right < mid) {
ans += (mid - cur.right) * 2;
left++;
}
else if (cur.left > mid) {
ans += (cur.left - mid) * 2;
right++;
}
else if (cur.left<start && cur.right>start) {
vec->erase(vec->begin() + i);
i--;
}
}
//cout << left << " " << right << " " << endl << "ans : " << ans << endl;
if (right == left || start == end) {
//cout << mid << endl;
return ans;
}
else if (right > left) {
return bs(mid + 1, end, vec, start_ans);
}
else {
return bs(start, mid, vec, start_ans);
}
}
int main()
{
int n, k, ans;
cin >> k >> n;
ans = 0;
vector<way> vec;
int n1, n2;
char t1, t2;
int max = 0;
int min = 1000000001;
for (int i = 0; i < n; i++) {
cin >> t1 >> n1 >> t2 >> n2;
ans += abs(n1 - n2);
if (t1 != t2) {
ans++;
way w = way(n1, n2);
if (w.left < min) min = w.left;
if (w.right > max) max = w.right;
vec.push_back(w);
}
}
if (k == 1) {
cout << bs(min, max, &vec, ans) << endl;
}
}