結果

問題 No.873 バイナリ、ヤバいなり！ｗ
ユーザー rlangevinrlangevin
提出日時 2023-10-19 12:49:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,326 bytes
コンパイル時間 989 ms
コンパイル使用メモリ 81,420 KB
実行使用メモリ 75,568 KB
最終ジャッジ日時 2023-10-19 12:50:04
合計ジャッジ時間 12,034 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 411 ms
75,368 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 35 ms
53,324 KB
testcase_06 AC 39 ms
53,544 KB
testcase_07 AC 35 ms
53,544 KB
testcase_08 AC 207 ms
75,492 KB
testcase_09 AC 34 ms
53,544 KB
testcase_10 AC 35 ms
53,544 KB
testcase_11 AC 39 ms
53,544 KB
testcase_12 AC 92 ms
75,340 KB
testcase_13 AC 35 ms
53,544 KB
testcase_14 AC 37 ms
53,544 KB
testcase_15 AC 36 ms
53,544 KB
testcase_16 AC 36 ms
53,544 KB
testcase_17 AC 42 ms
53,544 KB
testcase_18 AC 40 ms
53,544 KB
testcase_19 AC 36 ms
53,544 KB
testcase_20 AC 36 ms
53,544 KB
testcase_21 AC 36 ms
53,544 KB
testcase_22 AC 36 ms
53,544 KB
testcase_23 AC 35 ms
53,544 KB
testcase_24 AC 36 ms
53,544 KB
testcase_25 AC 36 ms
53,544 KB
testcase_26 AC 35 ms
53,544 KB
testcase_27 AC 36 ms
53,544 KB
testcase_28 AC 36 ms
53,544 KB
testcase_29 AC 37 ms
53,544 KB
testcase_30 WA -
testcase_31 AC 36 ms
53,544 KB
testcase_32 AC 80 ms
75,328 KB
testcase_33 AC 59 ms
70,220 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 471 ms
75,364 KB
testcase_37 WA -
testcase_38 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    N = int(input())
    M = int(N ** 0.5) + 2
    temp = []
    minv = 10 ** 18
    # for a in range(1, M):
    #     A = a * a
    #     if A > N:
    #         break
    #     if A == N:
    #         if a == minv:
    #             temp.append([a])
    #         elif a < minv:
    #             temp = [[a]]

    # for a in range(1, M):
    #     A = a * a
    #     if A > N:
    #         break
    #     for b in range(a, M):
    #         B = b * b
    #         if A + B > N:
    #             break
    #         if A + B == N:
    #             if a + b == minv:
    #                 temp.append([a, b])
    #             elif a + b < minv:
    #                 temp = [[a, b]]

    # for a in range(1, M):
    #     A = a * a
    #     if A > N:
    #         break
    #     for b in range(a, M):
    #         B = b * b
    #         if A + B > N:
    #             break
    #         for c in range(b, M):
    #             C = c * c
    #             if A + B + C > N:
    #                 break
    #             if A + B + C== N:
    #                 if a + b + c == minv:
    #                     temp.append([a, b, c])
    #                 elif a + b + c < minv:
    #                     temp = [[a, b, c]]

                
    for a in range(1, M):
        A = a * a
        if A > N or a > minv:
            break
        if A == N:
            if a == minv:
                temp.append([a])
            elif a < minv:
                temp = [[a]]
                minv = a
            break

        for b in range(a, M):
            B = b * b
            if A + B > N or a + b > minv:
                break
            if A + B == N:
                if a + b == minv:
                    temp.append([a, b])
                elif a + b < minv:
                    temp = [[a, b]]
                    minv = a + b
                break

            for c in range(b, M):
                C = c * c
                if A + B + C > N or a + b + c > minv:
                    break
                if A + B + C== N:
                    if a + b + c == minv:
                        temp.append([a, b, c])
                    elif a + b + c < minv:
                        temp = [[a, b, c]]
                        minv = a + b + c
                    break

                for d in range(c, M):
                    D = d * d
                    if A + B + C + D > N or a + b + c + d > minv:
                        break
                    if A + B + C + D == N:
                        if a + b + c + d == minv:
                            temp.append([a, b, c, d])
                        elif a + b + c + d < minv:
                            temp = [[a, b, c, d]]
                            minv = a + b + c + d
                        break

    def f(t):
        L = [None] * len(t)
        for i in range(len(t)):
            L[i] = (-(t[i]%2), t[i] * (-1) ** int(t[i]%2 == 0))
        L.sort()
        lst = []
        now = 0
        for _, a in L:
            a = abs(a)
            for i in range(a):
                lst.append(str(now))
                now = 1 - now
            now = 1 - now
        return "".join(lst)

    ans = None
    for t in temp:
        if ans is None:
            ans = f(t)
        else:
            ans = min(ans, f(t))
    print(ans)

main()
0