Submission

Score: 100

User: 12345678

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-02-13 09:55:22

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

using namespace std;

pair<int, int> locate_dining_cars(int N) 
{
    int l=1, r=N;
    while (l<r)
    {
        int md=(l+r)/2; // the left side is abit smaller
        int side_query=compare_cars(l, r);
        if (side_query==0)
        {
            int lx=l, rx=md; // find first position that -1 or 0
            while (lx<rx)
            {
                int mdx=(lx+rx)/2;
                if (compare_cars(mdx, mdx+1)!=1) rx=mdx;
                else lx=mdx+1;
            }
            int a=lx, b=r-(a-l);
            return {a, b};
        }
        int mid_query=compare_cars(md, md+1);
        if (side_query==-1) // nearer to the left
        {
            if (mid_query==-1) r=md;
            else
            {
                int lx=md+1, rx=r; // find first position that -1
                while (lx<rx)
                {
                    int mdx=(lx+rx)/2;
                    if (compare_cars(mdx, mdx+1)==-1) rx=mdx;
                    else lx=mdx+1;
                }
                int b=lx;
                lx=l, rx=md; // find last position that compare(x-1, x)==1
                while (lx<rx)
                {
                    int mdx=(lx+rx+1)/2;
                    if (compare_cars(mdx-1, mdx)==1) lx=mdx;
                    else rx=mdx-1;
                }
                int a=lx;
                return {a, b};
            }
        }
        if (side_query==1) // nearer to the right
        {
            // cout<<"debug "<<md<<' '<<mid_query<<'\n';
            if (mid_query==1) l=md+1;
            else
            {
                int lx=md+1, rx=r; // find first position that -1
                while (lx<rx)
                {
                    int mdx=(lx+rx)/2;
                    if (compare_cars(mdx, mdx+1)==-1) rx=mdx;
                    else lx=mdx+1;
                }
                int b=lx;
                lx=l, rx=md; // find last position that compare(x-1, x)==1
                while (lx<rx)
                {
                    int mdx=(lx+rx+1)/2;
                    if (compare_cars(mdx-1, mdx)==1) lx=mdx;
                    else rx=mdx-1;
                }
                int a=lx;
                return {a, b};
            } 
        }
    }
    return {l ,l};
}