Submission #921944

#	Time	Username	Problem	Language	Result	Execution time	Memory
921944		Ludissey	Palembang Bridges (APIO15_bridge)	C++14	9 / 100	4 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;
vector<int> b;
vector<char> P;
vector<int> S;
vector<char> Q;
vector<int> T;

int compute(int x){
    int sum=0;
    for (int i = 0; i < N; i++)
    {
        if(P[i]!=Q[i]) sum+=abs(x-S[i])+1+abs(x-T[i]);
        else sum+=abs(S[i]-T[i]);
    }
    return sum;
}
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;
}
int checkwith1(int x1){
    int mn=1e12;
    int l=x1,r=(2*N)-1;
    while((r-l)>1){
        int midLEFT=l+(r-l)/3;
        int midRIGHT=r-(r-l)/3;
        if(calculate(b[x1], b[midLEFT])>calculate(b[x1], b[midRIGHT])){
            l=midLEFT+1;
        }else{
            r=midRIGHT-1;
        }
    }
    for (int j = l; j <= r; j++)
    {
        mn=min(mn,calculate(b[x1],b[j]));
    }
    return mn;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,k; cin >> k >> n;
    N=n;
    if(k==1){
        P.resize(n);
        S.resize(n);
        Q.resize(n);
        T.resize(n);
        N=n;
        for (int i = 0; i < n; i++){
            cin >> P[i] >> S[i] >> Q[i] >> T[i];
            if(P[i]!=Q[i]) {
                notSame.push_back({min(S[i],T[i]), max(S[i],T[i])});
            }
        }
        int l=0;
        int r=1e9;
        while((r-l)>1){
            int mid=(l+r)/2;
            int midLEFT=(l+mid)/2;
            int midRIGHT=(mid+1+r)/2;
            if(compute(midLEFT)>compute(midRIGHT)){
                l=mid;
            }else{
                r=mid;
            }
        }
        int mid=r;
        if(compute(l)<compute(r)) mid=l;
        int sum=0;
        for (int i = 0; i < n; i++)
        {
            if(P[i]!=Q[i]) sum+=abs(mid-S[i])+1+abs(mid-T[i]);
            else sum+=abs(S[i]-T[i]);
        }
        cout << sum<< "\n";
    }else{
        int sum=0;
        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(b.begin(),b.end());
        N=a.size();  
        int mn=1e12;
        if(N==0) mn=0;
        int l=0,r=(2*N)-1;
        while((r-l)>1){
            int midLEFT=l+(r-l)/3;
            int midRIGHT=r-(r-l)/3;
            if(checkwith1(midLEFT)>checkwith1(midRIGHT)){
                l=midLEFT+1;
            }else{
                r=midRIGHT-1;
            }
        }
        for (int j = l; j <= r; j++)
        {
            mn=min(mn,checkwith1(j));
        }
        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:30:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<traj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:101:41: warning: narrowing conversion of 'mid' from 'double' to 'long long int' [-Wnarrowing]
  101 |                 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