Submission

Score: 45

User: KantaponZ

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

Language: cpp

Time: 0.006 second

Submitted On: 2025-06-15 14:00:54

#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;
		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 = r - a + l;
			return {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) {
				b = bSearch(ll, rr);
				return {2 * mid - b + 1, b};
			}
			b = bSearch(ll, rr);
			ll = l, rr = 2 * mid - b;
			a = bSearch(ll, rr);
			return {a, b};
		}

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

    return make_pair(l, r);
}