結果

問題 No.1373 Directed Operations
ユーザー gew1fw
提出日時 2025-06-12 21:36:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,034 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 81,928 KB
実行使用メモリ 101,616 KB
最終ジャッジ日時 2025-06-12 21:39:21
合計ジャッジ時間 5,535 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    a_list = list(map(int, data[1:N]))
    
    # Represent R as a list of intervals, sorted by start
    R = [(1, 1)]
    # U is a sorted list of unassigned nodes
    U = list(range(2, N+1))
    
    x_choices = []
    
    for a in a_list:
        found = False
        # We need to find the minimal x in R such that x + a is in U
        min_y = R[0][0] + a
        max_y = R[-1][1] + a
        
        # Find in U the minimal y >= min_y and <= max_y
        idx = bisect.bisect_left(U, min_y)
        while idx < len(U):
            y = U[idx]
            if y > max_y:
                break
            x = y - a
            # Check if x is in R
            # Perform binary search to check if x is in R
            low = 0
            high = len(R) - 1
            in_R = False
            while low <= high:
                mid = (low + high) // 2
                s, e = R[mid]
                if s <= x <= e:
                    in_R = True
                    break
                elif x < s:
                    high = mid - 1
                else:
                    low = mid + 1
            if in_R:
                # Assign x to y
                x_choices.append(x)
                # Remove y from U
                del U[idx]
                # Add y to R
                # Find where to insert (y,y)
                # Check adjacent intervals
                new_interval = (y, y)
                # Insert into R
                # Find the position to insert
                insert_pos = 0
                while insert_pos < len(R):
                    if R[insert_pos][0] > new_interval[0]:
                        break
                    insert_pos += 1
                R.insert(insert_pos, new_interval)
                # Merge with previous if possible
                if insert_pos > 0 and R[insert_pos - 1][1] >= R[insert_pos][0] - 1:
                    # Merge
                    merged_start = R[insert_pos - 1][0]
                    merged_end = max(R[insert_pos - 1][1], R[insert_pos][1])
                    R.pop(insert_pos)
                    R.pop(insert_pos - 1)
                    R.insert(insert_pos - 1, (merged_start, merged_end))
                    insert_pos -= 1
                # Merge with next if possible
                if insert_pos < len(R) - 1 and R[insert_pos][1] >= R[insert_pos + 1][0] - 1:
                    # Merge
                    merged_start = R[insert_pos][0]
                    merged_end = max(R[insert_pos][1], R[insert_pos + 1][1])
                    R.pop(insert_pos + 1)
                    R.pop(insert_pos)
                    R.insert(insert_pos, (merged_start, merged_end))
                found = True
                break
            else:
                idx += 1
        if not found:
            print("NO")
            return
    
    print("YES")
    for x in x_choices:
        print(x)

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