結果

問題 No.1748 Parking Lot
ユーザー gew1fw
提出日時 2025-06-12 18:31:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,009 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 291,380 KB
最終ジャッジ日時 2025-06-12 18:31:17
合計ジャッジ時間 4,230 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7 WA * 1 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    n, k = map(int, sys.stdin.readline().split())
    if n == 1:
        print(k)
        return
    
    heap = []
    # We need to handle the left segment (1 to k-1) and right segment (k+1 to n)
    left_len = k - 1
    if left_len > 0:
        # The maximum comfort in left segment is left_len, parked at 1
        heapq.heappush(heap, (-left_len, 1, k-1, 0))  # (comfort, start, end, type)
    
    right_len = n - k
    if right_len > 0:
        # The maximum comfort in right segment is right_len, parked at n
        heapq.heappush(heap, (-right_len, k+1, n, 1))
    
    # Now handle the middle segments as they form
    rem = n - 1
    last_pos = k
    
    while rem > 0:
        current = heapq.heappop(heap)
        comfort = -current[0]
        a = current[1]
        b = current[2]
        type_ = current[3]
        
        if type_ == 0:
            # Leftmost segment, park at a (which is 1)
            pos = a
        elif type_ == 1:
            # Rightmost segment, park at b (which is n)
            pos = b
        else:
            # Middle segment, park at the position with maximum comfort
            # The maximum comfort is (b - a) // 2
            # The position is a + (b - a) // 2
            pos = a + (b - a) // 2
        
        last_pos = pos
        rem -= 1
        
        # Split the interval and push new intervals
        if type_ == 0 or type_ == 1:
            # For leftmost or rightmost segments, splitting creates a middle segment
            # For leftmost, the new segment is (pos+1, b)
            # For rightmost, the new segment is (a, pos-1)
            if type_ == 0:
                new_a = pos + 1
                new_b = b
            else:
                new_a = a
                new_b = pos - 1
            
            if new_a <= new_b:
                new_len = new_b - new_a + 1
                max_comfort = (new_len - 1) // 2
                if max_comfort > 0:
                    heapq.heappush(heap, (-max_comfort, new_a, new_b, 2))
                else:
                    heapq.heappush(heap, (-max_comfort, new_a, new_b, 2))
        else:
            # Middle segment splits into two
            # Left part: a to pos-1
            # Right part: pos+1 to b
            if a <= pos - 1:
                left_len = (pos - 1) - a + 1
                left_comfort = (left_len - 1) // 2
                if left_comfort > 0:
                    heapq.heappush(heap, (-left_comfort, a, pos-1, 2))
                else:
                    heapq.heappush(heap, (-left_comfort, a, pos-1, 2))
            
            if pos + 1 <= b:
                right_len = b - (pos + 1) + 1
                right_comfort = (right_len - 1) // 2
                if right_comfort > 0:
                    heapq.heappush(heap, (-right_comfort, pos+1, b, 2))
                else:
                    heapq.heappush(heap, (-right_comfort, pos+1, b, 2))
    
    print(last_pos)

if __name__ == "__main__":
    main()
0