結果

問題 No.1635 Let’s Sort Integers!!
ユーザー LyricalMaestro
提出日時 2025-01-27 02:53:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 419 ms / 2,000 ms
コード長 3,464 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 226,388 KB
最終ジャッジ日時 2025-01-27 02:54:03
合計ジャッジ時間 20,646 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 77
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2255

from collections import deque

def main():
    N, K = map(int, input().split())

    n_min = N - 1

    array1 = [i for i in range(2, N + 1)]
    array2 = [i for i in reversed(range(2, N + 1))]
    iter_array = []
    i1 = 0
    i2 = 0
    for i in range(N - 1):
        if i % 4 <= 1:
            iter_array.append(array2[i2])
            i2 += 1
        else:
            iter_array.append(array1[i1])
            i1 += 1

    # n_maxを求めるためにやる
    queue = deque()
    queue.append(1)
    for n in iter_array:
        l = abs(n - queue[0])
        r = abs(n - queue[-1])
        if l >= r:
            queue.appendleft(n)
        else:
            queue.append(n)
    
    n = queue.popleft()
    ans = 0
    while len(queue) > 0:
        d = queue.popleft()
        ans += abs(d - n)
        n = d
    n_max = ans
    if not (n_min <= K <= n_max):
        print(-1)
        return
    
    queue = deque()
    queue.append(1)
    used = [False] * (N + 1)
    used[1] = True
    for n in iter_array:
        l = abs(n - queue[0])
        r = abs(n - queue[-1])
        if l > r:
            if K >= l:
                queue.appendleft(n)
                used[n] = True
                K -= l
            else:
                # 左でダメなら
                is_ok = False
                if n > queue[0]:
                    if not used[queue[0] + K]:
                        used[queue[0] + K] = True
                        queue.appendleft(queue[0] + K)
                        is_ok = True
                else:
                    if not used[queue[0] - K]:
                        used[queue[0] - K] = True
                        queue.appendleft(queue[0] - K)
                        is_ok = True
                
                if not is_ok:
                    if n > queue[-1]:
                        used[queue[-1] + K] = True
                        queue.append(queue[-1] + K)
                    else:
                        used[queue[-1] - K] = True
                        queue.append(queue[-1] - K)
                K = 0
        else:
            if K >= r:
                queue.append(n)
                used[n] = True
                K -= r
            else:
                is_ok = False
                if n > queue[-1]:
                    if not  used[queue[-1] + K]:
                        used[queue[-1] + K] = True
                        queue.append(queue[-1] + K)
                        is_ok = True
                else:
                    if not used[queue[-1] - K]:
                        used[queue[-1] - K] = True
                        queue.append(queue[-1] - K)
                        is_ok = True
                if not is_ok:
                    if n > queue[0]:
                        used[queue[0] + K] = True
                        queue.appendleft(queue[0] + K)
                    else:
                        used[queue[0] - K] = True
                        queue.appendleft(queue[0] - K)

                K = 0
        if K == 0:
            break

    answer = []
    while queue[0] != 1:
        answer.append(queue.popleft())

    answer.append(queue.popleft())
    for i in range(1 , N + 1):
        if not used[i]:
            answer.append(i)
    
    while len(queue) > 0:
        answer.append(queue.popleft())
    
    print(" ".join(map(str, answer)))
        




    


            



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