#include <bits/stdc++.h>
using namespace std;
int k, n;
long long curans;
vector <int> h;
bool sorting(pair <int, int> a, pair <int, int> b){
return a.first + a.second < b.first + b.second;
}
int findmedian(vector<pair<int, int>> j){
vector <int> d;
for (int i = 0; i < j.size(); i++){
d.push_back(j[i].first);
d.push_back(j[i].second);
}
d.erase(remove(d.begin(), d.end(), -1), d.end());
sort (d.begin(), d.end());
if (d.size() == 0) return 0;
return (d[d.size() / 2] + d[d.size() / 2 - 1]) / 2;
}
int main(){
long long ans = 0, dans = 0;
int k, n;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> k >> n;
int a[n*2];
vector <int> z;
vector <pair<int,int>> v;
char b[n], d[n];
for (int i = 0; i < n; i++){
cin >> b[i] >> a[i*2] >> d[i] >> a[i*2+1];
if (b[i] == d[i]){
v.push_back({-1, -1});
z.push_back(-1);
z.push_back(-1);
}
else {
dans++;
v.push_back({a[i*2], a[i*2+1]});
z.push_back(a[i*2]);
z.push_back(a[i*2+1]);
}
if (a[i*2] > a[i*2+1]){
swap(a[i*2], a[i*2+1]);
}
dans += a[i*2+1] - a[i*2];
}
int f;
if (k == 1){
while (k--){
f = findmedian(v);
for (int i = 0; i < n; i++){
if (f >= a[i*2] && f <= a[i*2+1]){
v[i].first = -1;
v[i].second = -1;
}
}
}
for (int i = 0; i < n; i++){
if (b[i] == d[i]){
ans += a[i*2+1] - a[i*2];
}
else{
if (v[i].first == -1){
ans += a[i*2+1] - a[i*2] + 1;
}
else{
if (f < a[i*2]) ans += 1 + a[i*2+1] - a[i*2] + 2 * (a[i*2] - f);
if (f > a[i*2+1]) ans += 1 + a[i*2+1] - a[i*2] + 2 * (f - a[i*2+1]);
}
}
}
}
else{
ans = LLONG_MAX;
int f, g, c;
sort(v.begin(), v.end(), sorting);
vector <pair<int, int>>start(v.begin(), v.begin() + 1);
vector <pair<int, int>>ends(v.begin() + 1, v.end());
for (int N = 1; N <= n; N++){
h = z;
curans = dans;
if (N != 1){
start.push_back(v[N-1]);
ends.erase(ends.begin());
}
f = findmedian(start);
g = findmedian(ends);
for (int i = 0; i < n; i++){
if (f >= a[i*2] && f <= a[i*2+1]){
h[i*2] = -1;
h[i*2+1] = -1;
}
}
for (int i = 0; i < n; i++){
if (g >= a[i*2] && g <= a[i*2+1]){
h[i*2] = -1;
h[i*2+1] = -1;
}
}
int change = 0;
if (N == 1){
for (int i = 0; i < n; i++){
if (b[i] != d[i] && h[i*2] != -1){
if (f < a[i*2]) c = 2 * (a[i*2] - f);
else c = 2 * (f - a[i*2+1]);
if (g < a[i*2]) c = min(2 * (a[i*2] - g), c);
else c = min(2 * (g - a[i*2+1]), c);
}
}
}
else{
for (int i = 0; i < n; i++){
if (b[i] != d[i] && h[i*2] != -1){
if (f < a[i*2]) c = 2 * (a[i*2] - f);
else c = 2 * (f - a[i*2+1]);
if (g < a[i*2]) c = min(2 * (a[i*2] - g), c);
else c = min(2 * (g - a[i*2+1]), c);
}
}
}
ans = min(curans, ans);
}
}
cout << ans;
}
Compilation message
bridge.cpp: In function 'int findmedian(std::vector<std::pair<int, int> >)':
bridge.cpp:12:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for (int i = 0; i < j.size(); i++){
| ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:102:17: warning: unused variable 'change' [-Wunused-variable]
102 | int change = 0;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
388 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
13 ms |
5288 KB |
Output is correct |
| 13 |
Correct |
28 ms |
5872 KB |
Output is correct |
| 14 |
Correct |
29 ms |
4960 KB |
Output is correct |
| 15 |
Correct |
16 ms |
3532 KB |
Output is correct |
| 16 |
Correct |
16 ms |
5620 KB |
Output is correct |
| 17 |
Correct |
23 ms |
6240 KB |
Output is correct |
| 18 |
Correct |
26 ms |
5824 KB |
Output is correct |
| 19 |
Correct |
30 ms |
5968 KB |
Output is correct |
| 20 |
Correct |
20 ms |
5664 KB |
Output is correct |
| 21 |
Correct |
25 ms |
5848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
