結果

問題 No.3271 PQ Dot Product
ユーザー apricity
提出日時 2025-08-10 18:07:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 137 ms / 1,000 ms
コード長 1,115 bytes
コンパイル時間 2,451 ms
コンパイル使用メモリ 81,824 KB
実行使用メモリ 98,128 KB
最終ジャッジ日時 2025-09-12 01:33:02
合計ジャッジ時間 8,726 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import permutations

def solve(n, k):
    if n < 4:
        for a in permutations(range(1,n+1)):
            x = sum((i+1)*a[i] for i in range(n))
            if x == k:
                return list(a)
        return [-1]

    ans = [0 for _ in range(n)]
    delta = [0 for _ in range(n+1)]
    for m in range(n,4,-1):
        if k <= m + (m-1)*m*(m+1)//3:
            ans[n-m] = m
            k -= m*(m+1)//2
        else:
            ans[n-m] = 1
            delta[n-m+1] = 1
            k -= m*m

    for a in permutations(range(1,5)):
        x = sum((i+1)*a[i] for i in range(4))
        if x == k:
            for i in range(4):
                ans[n-4+i] = a[i]
            break

    for i in range(n):
        ans[i] += delta[i]
        delta[i+1] += delta[i]
    return ans

N, K = map(int, input().split())
mx = sum(i*i for i in range(1, N+1))
mn = sum(i*(N+1-i) for i in range(1, N+1))
if K < mn or mx < K:
    print("No")
else:
    ans = solve(N, K)
    if ans == [-1]:
        print("No")
    else:
        print("Yes")
        print(*list(i for i in range(1, N+1)))
        print(*ans)
0