結果
| 問題 |
No.1568 Sushi
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:25:20 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,246 bytes |
| コンパイル時間 | 166 ms |
| コンパイル使用メモリ | 82,768 KB |
| 実行使用メモリ | 52,992 KB |
| 最終ジャッジ日時 | 2025-05-14 13:26:24 |
| 合計ジャッジ時間 | 10,631 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | TLE * 1 -- * 24 |
ソースコード
import sys
def solve():
L, N, Q = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
# Precompute displacements and directions
# d_at_A[i] = displacement at time A[i] (using A[-1]=0)
# current_A_times includes 0 and all A_i
# current_d_values[k] is d(current_A_times[k])
# current_dirs[k] is direction in [current_A_times[k], current_A_times[k+1])
current_A_times = [0] + A
num_segments = N + 1 # N intervals defined by N+1 points (0, A_0 ... A_{N-1})
current_d_values = [0] * (N + 1)
current_dirs = [0] * (N + 1)
current_disp = 0
current_time = 0
direction = 1 # 1 for CCW, -1 for CW
for i in range(N): # Iterating through N switches at A[0]...A[N-1]
# Interval [current_time, A[i])
# current_A_times[i] is previous A_time (or 0)
# current_A_times[i+1] is A[i]
# Displacement and direction for interval [current_A_times[i], current_A_times[i+1])
# which is [ A_{i-1} (or 0), A_i )
current_d_values[i] = current_disp
current_dirs[i] = direction
segment_duration = A[i] - current_time
current_disp += direction * segment_duration
current_time = A[i]
direction *= -1
# Last segment: from A[N-1] to infinity
current_d_values[N] = current_disp
current_dirs[N] = direction
# Function to get d(t)
def get_displacement_at_time(t):
if t == 0:
return 0
# Find segment for t
# Binary search for k such that current_A_times[k] <= t < current_A_times[k+1]
# A_times = [0, A_0, A_1, ..., A_{N-1}]
# N = len(A), current_A_times has N+1 elements from index 0 to N
import bisect
# k is such that current_A_times[k] is the latest change point <= t
# if t is one of A_i, then it falls into the start of the segment A_i to A_{i+1}
# bisect_right returns insertion point, k-1 is the index
k = bisect.bisect_right(current_A_times, t) -1
# if t itself is an A_i, k will be its index in current_A_times
# e.g. t=A[0], current_A_times = [0, A[0], ...], k=1
# d_base = current_d_values[k] which is d(current_A_times[k])
# dir_seg = current_dirs[k]
# time_in_seg = t - current_A_times[k]
# disp = d_base + dir_seg * time_in_seg
base_time_of_segment = current_A_times[k]
base_disp_of_segment = current_d_values[k]
dir_in_segment = current_dirs[k]
return base_disp_of_segment + dir_in_segment * (t - base_time_of_segment)
# Function to find smallest t_pickup >= t_place
# such that (d(t_pickup) - d(t_place)) % L == x_customer
# This means d(t_pickup) % L == (x_customer + d(t_place)) % L
def find_t_pickup(t_place, x_customer_target_chair, d_at_t_place):
if x_customer_target_chair == 0: # Takes 0 time if already at chair 0
# This case means sushi is placed at chair 0, customer is at chair 0.
# The time for sushi to travel from 0 to 0 is 0.
# So t_pickup = t_place.
return t_place
target_d_mod_L = (x_customer_target_chair + d_at_t_place % L + L) % L
min_t_found = float('inf')
# Check k = k_approx-1, k_approx, k_approx+1
# k_approx tries to make target_d_mod_L + k*L close to d_at_t_place
# (or rather, d(t_pickup) is close to d(t_place))
# So target_d_mod_L + k*L should be close to d_at_t_place
# Initial estimate for d_at_t_pickup is d_at_t_place + x_customer_target_chair (short CCW path)
# or d_at_t_place - (L - x_customer_target_chair) (short CW path)
# Estimate k for d(t_pickup) = target_d_mod_L + k * L
# If no direction changes, d(t_pickup) ~ d_at_t_place + (t_pickup - t_place)
# t_pickup - t_place is roughly x_customer_target_chair or L - x_customer_target_chair
# So d(t_pickup) ~ d_at_t_place + x_customer_target_chair OR d_at_t_place - (L - x_customer_target_chair)
# Let initial_abs_disp_estimate = d_at_t_place.
# k_center = round((initial_abs_disp_estimate - target_d_mod_L) / L) if L > 0 else 0
# A simpler approach: the actual displacement d(t_f) - d(t_s) will be one of
# x, x-L, x+L. (small number of laps)
# So d(t_f) will be d(t_s) + x, or d(t_s) + x-L, or d(t_s) + x+L.
# Iterate through possible absolute displacements d(t_f)
# for delta_disp_target in [x_customer_target_chair, x_customer_target_chair - L, x_customer_target_chair + L]:
# abs_target_d_val = d_at_t_place + delta_disp_target
# We need d(t) = target_d_mod_L + k*L
# Let's estimate k. d(t) should be roughly d(t_place).
# So target_d_mod_L + k*L approx d(t_place)
k_base = 0
if L > 0:
k_base = round((d_at_t_place - target_d_mod_L) / L)
for k_offset in [-2, -1, 0, 1, 2]: # Check a few k values around estimate
# The problem constraints on L and A_i are large,
# this range of k should be sufficient for typical scenarios
# where sushi does not make excessive laps.
# A more robust k range could be needed based on L and max travel time.
# Max travel time could be L. So relative displacement is up to L.
# d(t_f) - d(t_s) can be X, X-L, X+L.
# D(t_f) = D(t_s) + X, D(t_s) + X-L, D(t_s) + X+L
# D(t_f) = target_mod_L + k*L
# So target_mod_L + k*L = D(t_s) + X (or X-L or X+L)
# target_mod_L + k*L = ((target_mod_L - X) % L + L)%L + D_ts_multiple_of_L + X
# This means k*L should be near D_ts_multiple_of_L.
# So k should be near D_ts_multiple_of_L / L.
abs_target_d_val = target_d_mod_L + (k_base + k_offset) * L
# Find smallest t >= t_place such that d(t) = abs_target_d_val
# Find segment for t_place
import bisect
seg_idx_start = bisect.bisect_right(current_A_times, t_place) - 1
current_t_candidate = float('inf')
for j in range(seg_idx_start, N + 1):
seg_A_time = current_A_times[j]
seg_d_val = current_d_values[j]
seg_dir = current_dirs[j]
# Equation: seg_d_val + seg_dir * (t - seg_A_time) = abs_target_d_val
# seg_dir * (t - seg_A_time) = abs_target_d_val - seg_d_val
if seg_dir == 0: # Should not happen if L > 0 speed is 1
if seg_d_val == abs_target_d_val:
# Stays at this displacement for whole segment
# Smallest t is max(t_place, seg_A_time)
t_sol = max(t_place, seg_A_time)
if j < N : # has a next segment
if t_sol < current_A_times[j+1]:
current_t_candidate = min(current_t_candidate, t_sol)
break
else: # last segment
current_t_candidate = min(current_t_candidate, t_sol)
break
continue
# t - seg_A_time = (abs_target_d_val - seg_d_val) / seg_dir
# t = seg_A_time + (abs_target_d_val - seg_d_val) / seg_dir
# (abs_target_d_val - seg_d_val) must be multiple of seg_dir (i.e. same sign or zero) for t >= seg_A_time
# Or, more simply, (abs_target_d_val - seg_d_val) * seg_dir >= 0
if seg_dir == 1:
time_offset_in_seg = abs_target_d_val - seg_d_val
else: # seg_dir == -1
time_offset_in_seg = -(abs_target_d_val - seg_d_val) # i.e. seg_d_val - abs_target_d_val
if time_offset_in_seg < 0: # Target d_val already passed in this direction
continue
t_sol = seg_A_time + time_offset_in_seg
# Check if t_sol is valid for this segment and >= t_place
# Valid for segment: seg_A_time <= t_sol < next_A_time (if exists)
# Valid for search: t_sol >= t_place
actual_t_sol_start = max(t_place, seg_A_time)
if t_sol < actual_t_sol_start : # Solution is before we care
continue
seg_end_A_time = float('inf')
if j < N : # N is index of last segment start (A[N-1]), N+1 is total segments
seg_end_A_time = current_A_times[j+1]
if t_sol < seg_end_A_time:
current_t_candidate = min(current_t_candidate, t_sol)
break # Found in this segment, it's the earliest for this D_absolute
min_t_found = min(min_t_found, current_t_candidate)
return min_t_found
prev_ans = 0
results = []
for q_idx in range(Q):
B_i, C_i = map(int, sys.stdin.readline().split())
x_i_actual = 0
t_i_actual = 0
if q_idx == 0:
x_i_actual = B_i
t_i_actual = C_i
else:
x_i_actual = (B_i + prev_ans) % L
t_i_actual = (C_i + prev_ans) % (10**15)
if x_i_actual == 0: # Special case as discussed
current_ans = 0
results.append(current_ans)
prev_ans = current_ans
continue
# Candidates for t_place: t_i_actual, and potentially first A_j >= t_i_actual
t_place_candidates = [t_i_actual]
import bisect
first_A_idx_after_ti = bisect.bisect_left(A, t_i_actual) # index in original A
if first_A_idx_after_ti < N: # A[first_A_idx_after_ti] is an A_j >= t_i_actual
if A[first_A_idx_after_ti] > t_i_actual : # only consider if it's strictly after. If A[idx] == t_i_actual, it's covered by t_i_actual effects
t_place_candidates.append(A[first_A_idx_after_ti])
min_total_time_elapsed = float('inf')
for t_place_cand in t_place_candidates:
d_at_t_place_cand = get_displacement_at_time(t_place_cand)
t_pickup_cand = find_t_pickup(t_place_cand, x_i_actual, d_at_t_place_cand)
if t_pickup_cand != float('inf'):
time_elapsed = t_pickup_cand - t_i_actual
min_total_time_elapsed = min(min_total_time_elapsed, time_elapsed)
current_ans = min_total_time_elapsed
results.append(current_ans)
prev_ans = current_ans
for res in results:
sys.stdout.write(str(res) + "\n")
solve()