#include <bits/stdc++.h>
using namespace std;
int k, n;
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;
priority_queue <int> q;
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 {
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;
long long xans;
int f = -1, g = -1, af, ag, 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++){
if (f != -1){
af = f;
ag = g;
}
vector <int> h = z;
long long curans = dans;
if (N != 1){
start.push_back(v[N-1]);
ends.erase(ends.begin());
if (v[N-1].first >= f && v[N-1].second >= f) f = findmedian(start);
else if (v[N-1].first <= f && v[N-1].second <= f) f = findmedian(start);
if (v[N-1].first >= g && v[N-1].second >= g) g = findmedian(ends);
else if (v[N-1].first <= g && v[N-1].second <= g) g = findmedian(ends);
}
else{
f = findmedian(start);
g = findmedian(ends);
}
if (af != f || ag != g){
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;
}
}
for (int i = 0; i < n; i++){
if (b[i] != d[i]){
if (h[i*2] == -1){
curans += 1;
}
else{
if (f < a[i*2]) c = 1 + 2 * (a[i*2] - f);
else c = 1 + 2 * (f - a[i*2+1]);
if (g < a[i*2]) c = min(1 + 2 * (a[i*2] - g), c);
else c = min(1 + 2 * (g - a[i*2+1]), c);
curans += c;
}
}
}
if (curans < ans){
cout << ans;
return 0;
}
ans = min(curans, ans);
}
}
}
cout << ans;
}
Compilation message
bridge.cpp: In function 'int findmedian(std::vector<std::pair<int, int> >)':
bridge.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for (int i = 0; i < j.size(); i++){
| ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:75:19: warning: unused variable 'xans' [-Wunused-variable]
75 | long long xans;
| ^~~~
bridge.cpp:99:27: warning: 'ag' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | if (af != f || ag != g){
| ~~~^~~~
bridge.cpp:99:16: warning: 'af' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | if (af != f || ag != g){
| ~~~^~~~
| # |
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 |
1 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 |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 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 |
| 12 |
Correct |
16 ms |
6028 KB |
Output is correct |
| 13 |
Correct |
28 ms |
7616 KB |
Output is correct |
| 14 |
Correct |
24 ms |
6088 KB |
Output is correct |
| 15 |
Correct |
18 ms |
4560 KB |
Output is correct |
| 16 |
Correct |
18 ms |
6980 KB |
Output is correct |
| 17 |
Correct |
18 ms |
7492 KB |
Output is correct |
| 18 |
Correct |
22 ms |
7112 KB |
Output is correct |
| 19 |
Correct |
26 ms |
7560 KB |
Output is correct |
| 20 |
Correct |
18 ms |
7112 KB |
Output is correct |
| 21 |
Correct |
24 ms |
7360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
