Submission #921813

#	Time	Username	Problem	Language	Result	Execution time	Memory
921813		Ludissey	Palembang Bridges (APIO15_bridge)	C++14	9 / 100	226 ms	600 KiB

bridge

#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;
    int mid; 
};
vector<traj> a;

int calculate(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{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)/2;
            int midRIGHT=(mid+1+r)/2;
            if(calculate(b[i], b[midLEFT])>calculate(b[i], b[midRIGHT])){
                l=midLEFT+1;
            }else{
                r=midRIGHT-1;
            }
        }
        for (int j = l; j <= r; j++)
        {
            if(mn>calculate(b[i],b[j])) { 
                BESTL=b[i]; BESTR=b[j]; 
            }
            mn=min(mn,calculate(b[i],b[j]));
        }
    }
    cerr << BESTL << " " << BESTR <<"\n";

    cout << mn+sum << "\n";
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'long long int calculate(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++)
      |                     ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:36:37: warning: narrowing conversion of 'mid' from 'double' to 'long long int' [-Wnarrowing]
   36 |             traj element=traj{s, t, mid};
      |                                     ^~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 9 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37