#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int>> notSame; // min et le max
int N;
struct traj {
int l,r;
double mid;
};
vector<traj> a;
int cmp(int x1, int x2){
int s=0;
for (int i = 0; i < a.size(); i++)
{
int s1=abs(x1-a[i].l)+1+abs(x1-a[i].r);
int s2=abs(x2-a[i].l)+1+abs(x2-a[i].r);
s+=min(s1,s2);
}
return s;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n,k; cin >> k >> n;
N=n;
int sum=0;
vector<int> b;
for (int i = 0; i < n; i++){
char p,q; int s,t; cin >> p >> s >> q >> t;
if(p!=q) {
double mid=(((double)s+(double)t)/(double)2);
traj element=traj{min(s, t), max(s,t), mid};
a.push_back(element);
b.push_back(s);
b.push_back(t);
}else {
sum+=abs(s-t);
}
}
sort(a.begin(),a.end(),[](traj &_a, traj &_b){ return _a.mid < _b.mid; });
sort(b.begin(),b.end());
N=a.size();
int mn=1e12;
int BESTL, BESTR;
if(N==0) mn=0;
for (int i = 0; i < 2*N; i++)
{
int l=i+1,r=(2*N)-1;
while((r-l)>10){
int mid=(l+r)/2;
int midLEFT=(l+mid);
int midRIGHT=(mid+1+r)/2;
if(cmp(b[i], b[midLEFT])>cmp(b[i], b[midRIGHT])){
l=midLEFT+1;
}else{
r=midRIGHT-1;
}
}
for (int j = l; j <= r; j++)
{
if(mn>cmp(b[i],b[j])) {
BESTL=b[i]; BESTR=b[j];
}
mn=min(mn,cmp(b[i],b[j]));
}
}
cerr << BESTL << " " << BESTR <<"\n";
cout << mn+sum << "\n";
return 0;
}
Compilation message
bridge.cpp: In function 'long long int cmp(long long int, long long int)':
bridge.cpp:16:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<traj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
# |
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 |
142 ms |
348 KB |
Output is correct |
4 |
Incorrect |
64 ms |
344 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
140 ms |
500 KB |
Output is correct |
4 |
Incorrect |
64 ms |
512 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 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 |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |