Submission

Score: 21

User: exoworldgd

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-11-09 00:06:57

#pragma GCC optimize("O5,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include "dining_car.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define exoworldgd cin.tie(0)->sync_with_stdio(0), cout.tie(0)
using namespace std;
const int inf = LLONG_MAX, mod = 1e9+7, maxn = 1e5+5;
int compare_cars(int p, int q);
int find(int l, int r) {
    int mid,cmp;
    while (l < r) mid=(l+r)/2, cmp=compare_cars(mid,mid+1), cmp==-1 ? r=mid : l=mid+1;
    return l;
}
pii locate_dining_cars(int n) {
    int l=1,r=n,a,b;
    while (l < r) {
        int m = (l+r)/2, res = compare_cars(l,r);
        if (!res) {
            a = find(l+1,m), b = find(m+1,r);
            return a < b ? pii{a,b} : pii{b,a};
        }
        int mr = compare_cars(m,m+1);
        if (res == -1) {
            if (mr == -1) r=m;
            else {
                b = find(m+1,r), a = find(l,2*m-b > l ? 2*m-b : l);
                return pii{a,b};
            }
        } else {
            if (!mr) {
                a = find(l,m), b = find(m+1,r);
                return a < b ? pii{a,b} : pii{b,a};
            } else if (mr == -1) {
                int a = find(l,m), b = find(2*m+2-a < m+1 ? m+1 : 2*m+2-a,r);
                return pii{a,b};
            } else l=m+1;
        }
    }
    return pii{l,l+1};
}