Submission

Score: 0

User: usman

Problemset: รถไฟตู้เสบียง (Dining Car)

Language: cpp

Time: 0.001 second

Submitted On: 2025-05-25 02:14:51

#include <bits/stdc++.h>
#include "dining_car.h"

using namespace std;
pair < int, int > locate_dining_cars(int N)
{
    int l=1,r=N-1,cnt=0;
    while(l<=r){
        int m=(l+r)>>1;
        int rs=compare_cars(m,m+1);
        cnt++;
        if(rs>-1)l=m+1;
        else r=m-1;
    }l++;int lf=0,rg=0;
    if(l==1)lf=1;
    else if(l==N)rg=1;
    else if(abs(l-1)<abs(N-l)){
        int rs=compare_cars(l-abs(l-1),l+abs(l-1));
        if(rs!=-1)lf=1;
        else rg=1;
    }
    else {
        int rs=compare_cars(l-abs(N-l),l+abs(N-l));
        if(rs==1)lf=1;
        else rg=1;
    }
    if(lf==1){
        int tl=l+1,tr=N;
        while(tl<=tr){
            int m=(tl+tr)>>1;
            int rs=compare_cars(m,m+1);
            if(rs==-1)tr=m-1;
            else tl=m+1;
        }return make_pair(l,tl);
    }
    else if(rg==1){
        int tl=1,tr=l-1;
        while(tl<=tr){
            int m=(tl+tr)>>1;
            int rs=compare_cars(m,m+1);
            if(rs==-1||rs==0)tr=m-1;
            else tl=m+1;
        }return make_pair(tl,l);
    }
}