Submission

Score: 12

User: Pera

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-09-10 10:35:57

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

using namespace std;

static map<int, int> memo_g;

static int ask_compare(int p, int q) {
    if (p == q) return 0;
    return compare_cars(p, q);
}

static int get_g(int x, int N) {
    if (x <= 0) return 1;
    if (x >= N) return -1;
    auto it = memo_g.find(x);
    if (it != memo_g.end()) return it->second;
    return memo_g[x] = ask_compare(x, x + 1);
}

pair<int, int> locate_dining_cars(int N) {
    memo_g.clear();

    // Step 1: Find one dining car X in at most 30 queries
    int L = 0, R = N;
    while (R - L > 1) {
        int mid = L + (R - L) / 2;
        int res = get_g(mid, N);
        if (res >= 0) {
            L = mid;
        } else {
            R = mid;
        }
    }
    int X = R; // X is either A or B

    // Step 2: Determine whether X is A or B in at most 1 query
    bool is_A = false;
    if (X == 1) {
        is_A = true;
    } else if (X == N) {
        is_A = false;
    } else {
        if (X - 1 <= N - X) {
            int res = ask_compare(1, 2 * X - 1);
            is_A = (res != -1);
        } else {
            int res = ask_compare(N, 2 * X - N);
            is_A = (res == -1);
        }
    }

    // Step 3: Find the other dining car
    if (is_A) {
        int A = X;
        int low = A, high = N;

        while (high - low > 1) {
            int target = low + (high - low) / 2;
            int mid = target;

            // Check if a query inside (low, high) is already cached
            auto it = memo_g.upper_bound(low);
            if (it != memo_g.end() && it->first < high) {
                int best_p = it->first;
                int best_diff = abs(best_p - target);
                while (it != memo_g.end() && it->first < high) {
                    if (abs(it->first - target) < best_diff) {
                        best_diff = abs(it->first - target);
                        best_p = it->first;
                    }
                    ++it;
                }
                // Reuse cached point if it reasonably bifurcates the search interval
                if (best_diff <= (high - low) / 4) {
                    mid = best_p;
                }
            }

            int res = get_g(mid, N);
            if (res == 0) {
                if (mid == A) {
                    return {A, A + 1};
                } else {
                    int B = 2 * mid + 1 - A;
                    return {A, B};
                }
            } else if (res > 0) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return {A, high};
    } else {
        int B = X;
        int low = 0, high = B;

        while (high - low > 1) {
            int target = low + (high - low) / 2;
            int mid = target;

            auto it = memo_g.upper_bound(low);
            if (it != memo_g.end() && it->first < high) {
                int best_p = it->first;
                int best_diff = abs(best_p - target);
                while (it != memo_g.end() && it->first < high) {
                    if (abs(it->first - target) < best_diff) {
                        best_diff = abs(it->first - target);
                        best_p = it->first;
                    }
                    ++it;
                }
                if (best_diff <= (high - low) / 4) {
                    mid = best_p;
                }
            }

            int res = get_g(mid, N);
            if (res == 0) {
                if (mid == B - 1) {
                    return {B - 1, B};
                } else {
                    int A = 2 * mid + 1 - B;
                    return {A, B};
                }
            } else if (res > 0) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return {high, B};
    }
}