Submission

Score: 0

User: mzmvtbgf

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

Language: cpp

Time: 0.001 second

Submitted On: 2026-04-24 16:15:22

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

using namespace std;

// you can also write additional functions here

// int N, A, B;
// int calls_cnt;

// void quit(const char* message) {
//   printf("%s\n", message);
//   exit(0);
// }


// int calc_dist(int i){
// 	return std::min(std::abs(i-A),std::abs(i-B));
// }

// int compare_cars(int i, int j){
// 	calls_cnt++;
//   cout << i << " " << j << " \n";
// 	if (calls_cnt > 60)
// 		quit("Too many calls");
// 	if (i<1 || i>N || j<1 || j>N)
// 		quit("Invalid argument");
	
// 	int dist_i = calc_dist(i);
// 	int dist_j = calc_dist(j);
	
// 	if(dist_i < dist_j)
// 		return -1;
// 	if(dist_i == dist_j)
// 		return 0;
// 	return 1;
// }

pair<int,int> locate_dining_cars(int N)
{
    pair<int, int> ans = {0,0};
    int left = 1;
    int right = N;
    int x = -1;
    while (left < right)
    {
        int mid = left + (right-left)/2;
        int aa = compare_cars(mid-1, mid + 1);
        if (aa == -1)
        {
          right = mid - 1;
        }
        else if (aa == 0)
        {
          left = mid;
          break;
        }
        else left = mid + 1;
    }
    ans.first = left;
    x = left;
    // cout << x << "\n";
    if (compare_cars(x/2, x/2 + N/2) > -1)
    {
        left = 1;
        right = x-1;
    }
    else 
    {
        left = x + 1;
        right = N;
    }
    // cout << left << "  " << right << "\n";
    while (left < right)
    {
        int mid = left + (right-left)/2;
        int sec1 = left + (mid-left)/2;
        int sec2 = mid + (right-mid)/2;
        int aa = compare_cars(sec1, sec2);
        if (sec2 - sec1 == 1)
        {
          if (aa == -1) ans.second = sec1;
          else ans.second = sec2;
          break;
        }
        if (aa == 0)
        {
            ans.second = sec1 + (sec2-sec1)/2;
            break;
        }
        else if (aa == -1) right = mid + 1;
        else left = mid + 1;
    }
    return ans;
}

// int main() {
// 	scanf("%d%d%d",&N, &A, &B);
// 	std::pair<int, int> P = locate_dining_cars(N);
// 	printf("%d %d %d\n", P.first, P.second, calls_cnt);
	
// 	return 0;
// }