結果

問題 No.2608 Divide into two
コンテスト
ユーザー 添え字
提出日時 2024-01-19 21:50:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 523 ms / 1,000 ms
コード長 931 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 92,852 KB
最終ジャッジ日時 2024-09-28 04:19:28
合計ジャッジ時間 1,340 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        print(solve(N))


def solve(N):
    def tri(x):
        return x * (x + 1) // 2

    T = tri(N)
    if T & 1:
        return -1

    T = T // 2

    dp = [[(-1, -1)] * (T + 1) for _ in range(N + 1)]

    dp[0][0] = (0, -1)

    for i in range(1, N + 1):
        for j in range(T + 1):
            if dp[i - 1][j] != (-1, -1):
                dp[i][j] = dp[i - 1][j]
                continue
            if j - i >= 0:
                if dp[i - 1][j - i] != (-1, -1):
                    dp[i][j] = (i, dp[i - 1][j - i][0])

    if dp[N][T] == (-1, -1):
        return -1

    v, p = dp[N][T]
    res = [v]
    S = T
    while p != 0:
        S -= v
        v, p = dp[p][S]
        res.append(v)

    ans = [0] * (N + 1)
    for v in res[::-1]:
        ans[v] = 1

    return "".join(map(str, ans[1:]))


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