Submission

Score: 97

User: KantaponZ

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-06-15 14:39:42

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

using namespace std;


#define CC compare_cars

int bSearch(int l, int r) {
	while (l < r) {
        int mid = (l + r) / 2;
        if (mid + 1 > r) break;
		int x = CC(mid, mid + 1);
        if (x == 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 mid = (l + r) / 2;
		int x = CC(l, r);
		if (x == 0) {
			int a = bSearch(l, mid);
			int b = bSearch(mid + 1, r);
			return {min(a,b), max(a,b)};
		}

		int y = CC(mid, mid + 1);
		if (x == -1) {
            if (y == -1) {
				r = mid;
				continue;
			}
			int ll = mid + 1, rr = r, a, b;
			if (y == 0) {
				a = bSearch(l, mid);
				b = bSearch(mid + 1, r);
				return {min(a,b), max(a,b)};
			}
			b = bSearch(ll, rr);
			ll = l, rr = 2 * mid - b;
			a = bSearch(ll, rr);
			return {min(a,b), max(a,b)};
		}

		if (x == 1) {
            if (y == 1) {
				l = mid + 1;
				continue;
			}
			int ll = l, rr = mid, a, b;
			if (y == 0) {
				a = bSearch(l, mid);
				b = bSearch(mid + 1, r);
				return {min(a,b), max(a,b)};
			}
			a = bSearch(ll, rr);
			ll = 2 * mid - a, rr = r;
			b = bSearch(ll, rr);
			return {min(a,b), max(a,b)};
		}
	}

    return make_pair(l, r);
}