Submission

Score: 100

User: kungarooo

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-11-01 00:50:40

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

using namespace std;
int a=-1,b=-1;
int bi2(int l,int r){
  //cout<<"l="<<l<<"r="<<r<<"\n";
  int e=r-l+1;
  int ll=l,rr=r;
  while(ll<rr){
    e=rr-ll+1;
    int lll=ll+e/2-1,rrr=rr-e/2+1;
    //cout<<lll<<" : "<<rrr<<"\n";
    int cmp=compare_cars(lll,rrr);
    if(cmp==0)return lll+1;
    if(cmp==-1){
      rr=lll;
    }else{
      ll=rrr;
    }
  }
  return ll;
}
int bi(int l,int r){
  int ll=l,rr=r;
  while(ll<rr){
    int e=rr-ll+1;
    int cmp=compare_cars(ll,rr);
    //cout<<ll<<" :: "<<rr<<"\n";
    if(cmp==0)return (ll+rr)/2;
    else if(cmp==-1){
      rr=ll+e/2-1;
    }else if(cmp==1){
      ll=rr-e/2+1;
    }
  }
  return ll;
}
void func2(int l,int r,int s){
  int e=r-l+1;
  int firsthalf=l+e/2-1,secondhalf=r-e/2+1;
  if(s==-1){
    a=bi(l,firsthalf);
    int dis=firsthalf-a;
    b=bi2(secondhalf,r);
  }
  else if(s==1){
    a=bi(secondhalf,r);
    int dis=a-secondhalf;
    b=bi2(l,firsthalf);
  }
}
void func1(int l,int r){
  //cout<<l<<" "<<r<<"\n";
  int e=(r-l)+1;
  if(e==2){
    a=l,b=r;
    return;
  }
  int f=compare_cars(l,r),s=compare_cars(l+e/2-1,r-e/2+1);
  if(e==3){
    if(f==1){
      a=l+1,b=r;
      return;
    }
    if(f==-1){
      a=l,b=l+1;
      return;
    }
    a=l,b=r;
    return;
  }
  if(f==-1&&s==-1){
    func1(l,l+e/2);
  }else if(f==1&&s==1){
    func1(r-e/2,r);
  }else if(s==0){
    if(f==-1&&s==0){
      a=l+e/2;
      b=bi2(l,l+e/2-1);
      return;
    }
    if(f==0&&s==0){
      a=bi2(l,l+e/2-1);
      int dis=l+e/2-1-a;
      b=r-e/2+1+dis;
      return;
    }
    if(f==1&&s==0){
      a=l+e/2;
      b=bi2(r-e/2+1,r);
      return;
    }
  }else{
    func2(l,r,s);
    return;
  }
  //write for edge case later
  //please account for tub trong pordee
}
pair < int, int > locate_dining_cars(int N) 
{
  func1(1,N);

  return make_pair(min(a,b),max(a,b));
}