Submission

Score: 61

User: Xapitize

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-20 21:54:01

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

using namespace std;

// ฟังก์ชันช่วยสำหรับทำ Binary Search หาจุดต่ำสุด (Local Minimum)
int find_min(int L, int R) {
    while (L < R) {
        int mid = L + (R - L) / 2;
        // ถ้า mid ไกลกว่า mid + 1 แสดงว่ากราฟกำลังดิ่งลงทางขวา
        if (compare_cars(mid, mid + 1) == 1) {
            L = mid + 1;
        } else {
            // กราฟเชิดขึ้นทางซ้าย หรือเป็นจุดสมมาตรพอดี
            R = mid;
        }
    }
    return L;
}

pair<int, int> locate_dining_cars(int N) {
    // 1. หาตู้เสบียงมาให้ได้ก่อน 1 ตู้ (จะเจอ A หรือ B ขึ้นอยู่กับจังหวะของ mid)
    int X = find_min(1, N);
    
    // 2. ลองค้นหาในโซนฝั่งซ้ายของ X ก่อน (ถ้ามีพื้นที่ให้หา)
    if (X > 1) {
        int Y = find_min(1, X - 1);
        
        // พิสูจน์ว่า Y เป็นตู้เสบียงจริงๆ หรือไม่
        // (X คือตู้เสบียงแน่นอน ถ้าระยะห่างเท่ากับ X แสดงว่า Y ก็เป็นตู้เสบียง)
        if (compare_cars(Y, X) == 0) {
            return make_pair(Y, X); // เจอครบแล้ว A=Y, B=X
        }
    }
    
    // 3. ถ้าฝั่งซ้ายไม่ใช่ตู้เสบียง แสดงว่าอีกตู้ต้องซ่อนอยู่ฝั่งขวาแน่นอน
    int Z = find_min(X + 1, N);
    return make_pair(X, Z); // เจอครบแล้ว A=X, B=Z
}