Submission

Score: 95

User: Ninstroyer

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-02-15 20:36:33

#include <bits/stdc++.h>
#include "dining_car.h"
using namespace std;

int findCar(int l, int r)
{
    while(l<r)
    {
        int md = (l+r)/2;
        if(compare_cars(md,md+1) <= 0) r = md;
        else l = md+1; 
    }
    return l;
}

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