結果

問題 No.1373 Directed Operations
ユーザー qwewe
提出日時 2025-04-24 12:21:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,907 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 96,916 KB
最終ジャッジ日時 2025-04-24 12:23:13
合計ジャッジ時間 4,473 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
a = list(map(int, input().split()))
reachable = [False] * (n + 2)
reachable[1] = True
current_max = 1
earliest_missing = 2
ans = []

for ai in a:
    if earliest_missing <= n:
        x = earliest_missing - ai
        if x >= 1 and reachable[x]:
            ans.append(x)
            reachable[earliest_missing] = True
            current_max = max(current_max, earliest_missing)
            while earliest_missing <= n and reachable[earliest_missing]:
                earliest_missing += 1
            continue
    # If not possible, choose x to be the largest possible
    x = min(current_max, n - ai)
    found = False
    if x >= 1 and reachable[x]:
        new_node = x + ai
        if new_node <= n and not reachable[new_node]:
            found = True
    if not found:
        x = -1
        # Find the largest x in reachable that can extend
        for x_candidate in range(min(current_max, n - ai), 0, -1):
            if reachable[x_candidate]:
                new_node = x_candidate + ai
                if new_node > n:
                    continue
                if not reachable[new_node]:
                    x = x_candidate
                    found = True
                    break
        if not found:
            # Choose any valid x, but it won't help
            for x_candidate in range(1, current_max + 1):
                if reachable[x_candidate] and x_candidate <= n - ai:
                    x = x_candidate
                    break
    ans.append(x)
    new_node = x + ai
    if new_node <= n and not reachable[new_node]:
        reachable[new_node] = True
        current_max = max(current_max, new_node)
        if new_node >= earliest_missing:
            while earliest_missing <= n and reachable[earliest_missing]:
                earliest_missing += 1

if earliest_missing > n:
    print("YES")
    print("\n".join(map(str, ans)))
else:
    print("NO")
0