Submission

Score: 100

User: Maxzyb0y

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-02-15 15:54:21

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

using namespace std;

int x,y;

int find_first_car(int l, int r) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        int c = compare_cars(mid, mid + 1);
        if (c == 1) {
            l = mid + 1;
        } 
        else 
        {
            r = mid;
        }
    }
    return l;
}

pair<int, int> locate_dining_cars(int N)
{
    int l=1, r=N;
    while (l<r)
    {
        int md = (l+r)/2;
        int side_query = compare_cars(l,r);
        if (side_query == 0)
        {
            x = find_first_car(l, md);
            y = r-(x-l);
            return {x, y};
        }
        int mid_query = compare_cars(md, md+1);
        if (side_query == -1 && mid_query == -1)
            r = md;
        else if (side_query == 1 && mid_query == 1)
            l = md+1;
        else
            return {find_first_car(l, md), find_first_car(md+1, r)};
    }
}