제출 #1213793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213793		Nelt	추월 (IOI23_overtaking)	C++17	100 / 100	2537 ms	137284 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

/*
  Ultra‑obfuscated, linker‑safe version.
  – Keeps public symbols:  init(), arrival_time()
  – All internal logic hidden in macros & lambdas.
  – Compile‑tested: no macro/parameter collisions, uniform lambda returns.
*/

#define T  long long
#define U  std::vector
#define P  std::pair
#define S  std::set
#define A  std::array
#define M  std::make_pair
#define B  begin()
#define E  end()
#define LB lower_bound      // renamed (was L) to avoid clash with init parameter L
#define UB upper_bound
#define F  for
#define W  while
#define IF if
#define R  return
#define C  const
#define Q  queue
#define D  dp               //   D[i][j]
#define PM  prev_mx         // P<T,T> array name
#define TTBL  ttbl         // time table
#define V  v
#define X  s
#define N  n
#define Y  m
#define Z  x_
#define INF 9000000000000000000LL

/* ─── Global storage (unchanged sizes) ─── */
T D[1005][1005];
P<T,T> PM[1005][1005];
T TTBL[1005][1005];
T V[1005];
T X[1005];
T N, Y, Z;
U<P<T,T>> TMP[1005];
S<A<T,3>> ST;

/* ─── Helpers ─── */
#define GP(x) ([&](){auto it=ST.UB({x,INF,INF});if(it!=ST.begin()){--it;if((*it)[1]>=x)R (*it)[2];}R (T)(-1);})()

#define ADD(l,r,z) ([&](){if((l)>(r))R;auto it=ST.LB({l,-INF,-INF});\
                     while(it!=ST.end()&&(*it)[1]<=r)it=ST.erase(it);\
                     if(it!=ST.end()&&(*it)[0]<=r){auto [a,b,c]=*it;ST.erase(it);ST.insert({r+1,b,c});}\
                     it=ST.LB({l,-INF,-INF});\
                     if(it!=ST.begin()){--it;if((*it)[1]>=l){auto [a,b,c]=*it;ST.erase(it);ST.insert({a,l-1,c});if(b>=r)ST.insert({r+1,b,c});}}\
                     ST.insert({l,r,z}); })()

/* ─── Mega‑macro: full initialisation ─── */
#define INIT_WRAPPER(LLEN,N0,T0,W0,X0,M0,S0) ([&](){\
    Z=X0; N=N0; Y=M0;\
    F(T i=0;i<N;++i) TTBL[i][0]=T0[i];\
    F(T i=0;i<N;++i) V[i]=W0[i];\
    V[N]=Z;\
    F(T i=0;i<Y;++i) X[i]=S0[i];\
    /* build layer 0 */ \
    F(T i=0;i<N;++i) TMP[0].emplace_back(M(TTBL[i][0],i));\
    std::sort(TMP[0].B,TMP[0].E);\
    /* forward layers */\
    F(T i=1;i<Y;++i){\
        F(T x=0;x<N;++x){\
            T j=TMP[i-1][x].second;\
            TTBL[j][i]=TTBL[j][i-1]+V[j]*(X[i]-X[i-1]);\
            PM[i][x]=std::max(x?PM[i][x-1]:M(0LL,0LL),M(TTBL[j][i],j));\
            T pos=LB(TMP[i-1].B,TMP[i-1].E,M(TTBL[j][i-1],-1LL))-TMP[i-1].B-1;\
            IF(pos>=0) TTBL[j][i]=std::max(TTBL[j][i],PM[i][pos].first);}\
        F(T j=0;j<N;++j) TMP[i].emplace_back(M(TTBL[j][i],j));\
        std::sort(TMP[i].B,TMP[i].E);}\
    /* backward DP & interval build */\
    for(T i=Y-1; ~i; --i){\
        F(T j=0;j<N;++j){\
            T pt=GP(TTBL[j][i]-X[i]*Z);\
            IF(pt==-1) D[i][j]=TTBL[j][i]+(LLEN-X[i])*Z;\
            else {\
                T last=TTBL[j][i]+(X[pt-1]-X[i])*Z;\
                T pos=LB(TMP[pt-1].B,TMP[pt-1].E,M(last,-1LL))-TMP[pt-1].B-1;\
                IF(pos>=0) D[i][j]=D[pt][PM[pt][pos].second];\
                else std::abort();}}\
        IF(i) F(T j=0;j<N;++j) ADD(TTBL[j][i-1]-X[i-1]*Z+1,TTBL[j][i]-X[i]*Z,i);} })()

/* ─── Query macro ─── */
#define ARRIVAL(x) ([&](){T pt=GP(x);IF(pt==-1)R x+X[Y-1]*Z;\
                          T last=x+X[pt-1]*Z;\
                          T pos=LB(TMP[pt-1].B,TMP[pt-1].E,M(last,-1LL))-TMP[pt-1].B-1;\
                          R D[pt][PM[pt][pos].second];})()

/* ─── Public wrappers required by grader ─── */
void init(int Llen,int N0,std::vector<long long> T0,std::vector<int> W0,int X0,int M0,std::vector<int> S0){ INIT_WRAPPER(Llen,N0,T0,W0,X0,M0,S0); }

long long arrival_time(long long cur){ return ARRIVAL(cur); }

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 35 / 35