Submission

Score: 21

User: Nagornz

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

Language: cpp

Time: 0.001 second

Submitted On: 2025-05-24 19:40:22

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

using namespace std;

int ask(int x, int y){
    return compare_cars(x, y);
}

int solve(int l, int r) {
    while (l < r) {
        int mid = (l + r) / 2;
        int x = ask(mid, mid + 1);
        if (x == -1) r = mid;
        else l = mid + 1;
    }
    return l;
}

pair <int32_t, int32_t> locate_dining_cars(int32_t n) {
    if (n == 2) return {1, 2};
    int l = 1, r = n;
    while (l < r) {
        int midd = (l + r) / 2;
        int x = ask(l, r);
        if (x == 0) {
            int a = solve(l, midd);
            int dist = midd - a;
            int b = midd + dist;
            return {min(a, b), max(a, b)};
        }
        int y = ask(midd, midd + 1);
        if (x == -1) {
            if (y == -1) r = midd;
            else { 
                int ll = midd + 1, rr = r, a, b;
                while (ll < rr) {
                    int mid = (ll + rr) / 2;
                    if (ask(mid, mid + 1) == -1) rr = mid;
                    else ll = mid + 1;
                }
                b = ll;
                ll = l, rr = 2 * midd - b;
                while (ll < rr) {
                    int mid = (ll + rr) / 2;
                    if (ask(mid, mid + 1) == -1) rr = mid;
                    else ll = mid + 1;
                }
                a = ll;
                return {min(a, b), max(a, b)};
            }
        } 
        else {
            if (y == 0) {
                int a = solve(l, midd);
                int b = 2 * midd - a;
                return {min(a, b), max(a, b)};
            } 
            else if (y == -1) {
                int ll = l, rr = midd, a, b;
                while (ll < rr) {
                    int mid = (ll + rr) / 2;
                    if (ask(mid, mid + 1) == -1) rr = mid;
                    else ll = mid + 1;
                }
                a = ll;
                ll = 2 * midd - a, rr = r;
                while (ll < rr) {
                    int mid = (ll + rr) / 2;
                    if (ask(mid, mid + 1) == -1) rr = mid;
                    else ll = mid + 1;
                }
                b = ll;
                return {min(a, b), max(a, b)};
            } 
            else l = midd + 1;
        }
    }
    return {l, r};
}