Submission

Score: 60

User: usman

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

Language: cpp

Time: 0.001 second

Submitted On: 2025-05-25 15:00:17

#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));cnt++;
        if(rs!=-1)lf=1;
        else rg=1;
    }
    else {
        int rs=compare_cars(l-abs(N-l),l+abs(N-l));cnt++;
        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(cnt==60){
                return make_pair(l,tl+rand()%2);
            }
            int rs=compare_cars(m,m+1);
            cnt++;
            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;
            if(cnt==60){
                return make_pair(tl+rand()%2,l);
            }
            int rs=compare_cars(m,m+1);
            cnt++;
            if(rs==-1||rs==0)tr=m;
            else tl=m+1;
        }return make_pair(tl,l);
    }
}