結果

問題 No.2929 Miracle Branch
コンテスト
ユーザー Yakumo221
提出日時 2024-10-12 15:45:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,716 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 65,536 KB
最終ジャッジ日時 2024-10-12 15:46:10
合計ジャッジ時間 4,535 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

# from math import isqrt
# from functools import cache
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 5)

def isqrt(n):
    ok = 0
    ng = 1 << 60
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if pow(mid,2) <= n:
            ok = mid
        else:
            ng = mid
    return mid

# @cache
def yakusu_rekkyo(n):
    if n in dic:
        return dic[n]
    
    low = []
    up = []
    for i in range(1, isqrt(n)+1):
        if n % i == 0:
            low.append(i)
            if n//i != i:
                up.append(n//i)
    ret = low + up[::-1]
    dic[n] = ret
    return ret

x = int(input())
if x == 1:
    print(2)
    print(1,2)
    print("b","g")
    exit()


dic = defaultdict(list)

ans_tot = [200001]
ans_bro = [0]
ans_gre = [[]]

tot = [0]
bro = [0]
gre = []

def func(x):
    if x == 1:
        if ans_tot[0] > tot[0]:
            # print(tot, bro, gre)
            ans_tot[0] = tot[0]
            ans_bro[0] = bro[0]
            ans_gre[0] = gre[:]
        
        return
    
    yakusu = yakusu_rekkyo(x)
    for y in yakusu:
        if y == 1:
            continue

        tot[0] += y+1
        bro[0] += 1
        gre.append(y)
        func(x//y)
        tot[0] -= y+1
        bro[0] -= 1
        gre.pop()

func(x)
ans_tot = ans_tot[0]
ans_bro = ans_bro[0]
ans_gre = ans_gre[0]
# print(ans_tot)
# print(ans_bro)
# print(ans_gre)

if ans_tot == 200001:
    print(-1)
    exit()


print(ans_tot)
for i in range(ans_bro-1):
    print(i+1, i+2)

cnt = ans_bro+1
for i in range(ans_bro):
    for j in range(ans_gre[i]):
        print(i+1, cnt)
        cnt += 1

col = ["g" for i in range(ans_tot)]
for i in range(ans_bro):
    col[i] = "b"

print(*col)
0