#include <bits/stdc++.h>
using namespace std;
#define pr pair<int, int>
#define ll long long
#define pb push_back
#define f first
#define s second
int main(){
int nb, n; cin>>nb>>n;
vector<pr> nlist;
ll dist1=0;
for (int i=0; i<n; i++){
char s1, num1, s2, num2;
cin>>s1>>num1>>s2>>num2;
if(s1==s2) dist1+=abs(num1-num2);
else{
if(num1>num2) swap(num1, num2);
nlist.push_back({num1, num2});
}
}
sort(nlist.begin(), nlist.end());
//=== two medium to calculate
n=nlist.size();
ll dist2=0;
multiset<int, greater<int>> r1;
multiset<int> r2;
for (int i=0; i<n; i++){
r1.insert(nlist[i].f); r1.insert(nlist[i].s);
}
while((int)r1.size()>n){
r2.insert(*r1.begin()); r1.erase(r1.begin());
}
dist2=0;
for (auto it=r1.begin(); it!=r1.end(); it++){
dist2+=abs(*it-*r1.begin());
}
for (auto it=r2.begin(); it!=r2.end(); it++){
dist2+=abs(*it-*r1.begin());
}
if(nb==1) {
cout<<dist2+dist1+n<<endl;
return 0;
}
multiset<int, greater<int>> lft1;
multiset<int> lft2;
ll dist=dist2;
int mid1=*r1.begin(); int mid2=0;
for (int i=0; i<n-1; i++){
int mid1new;
int elem1=nlist[i].f; int elem2=nlist[i].s;
dist-=abs(mid1-elem1)+abs(mid1-elem2);
if(r1.find(elem1)!=r1.end() && r1.find(elem2)!=r1.end() ){
r1.erase(r1.find(elem1)); r1.erase(r1.find(elem2));
r1.insert(*r2.begin()), r2.erase(r2.begin());
mid1new=*r1.begin();
dist-=2*(mid1new-mid1);
}
else if(r1.find(elem1)!=r1.end() && r1.find(elem2)!=r2.end()){
r1.erase(r1.find(elem1)); r2.erase(r2.find(elem2));
mid1new=*r1.begin();
}
else{
r2.erase(r2.find(elem1)); r2.erase(r2.find(elem2));
r2.insert(*r1.begin()); r1.erase(r1.begin());
mid1new=*r1.begin();
}
mid1=mid1new;
//
int mid2new;
dist+=abs(mid2-elem1)+abs(mid2-elem2);
if(elem1>mid2 && elem2>mid2){
lft2.insert(elem1); lft2.insert(elem2);
lft1.insert(*lft2.begin()); lft2.erase(lft2.begin());
mid2new=*lft1.begin();
dist-=2*(mid2new-mid2);
}
else if(elem1<=mid2 && elem2>mid2){
lft1.insert(elem1); lft2.insert(elem2);
}
else{
lft1.insert(elem1); lft1.insert(elem2);
lft2.insert(*lft1.begin()); lft1.erase(lft1.begin());
mid2new=*lft1.begin();
}
mid2=mid2new;
dist2=min(dist2, dist);
}
cout<<dist2+dist1+n<<endl;
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:89:23: warning: 'mid2new' may be used uninitialized in this function [-Wmaybe-uninitialized]
89 | else if(elem1<=mid2 && elem2>mid2){
| ~~~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 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 |
- |
