Submission

Score: 0

User: usman

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

Language: cpp

Time: 0.001 second

Submitted On: 2025-05-25 02:53:06

#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)>>1;
        int rs=compare_cars(m,m+1);
        cnt++;
        if(rs>-1)l=m;
        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;
            if(tr-tl<=3){
                int rs=compare_cars(tl,tl+2);
                if(rs==0)tl=tl+1;
                else if(rs==1)tl=tl+2;
                else tl=tl;
                break;
            }
            int rs=compare_cars(m,m+1);
            if(rs==-1)tr=m;
            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(tr-tl<=3){
                int rs=compare_cars(tl,tl+2);
                if(rs==0)tl=tl+1;
                else if(rs==1)tl=tl+2;
                else tl=tl;
                break;
            }
            if(rs==-1||rs==0)tr=m;
            else tl=m+1;
        }return make_pair(tl,l);
    }
}