結果
問題 | No.2929 Miracle Branch |
ユーザー |
![]() |
提出日時 | 2024-10-12 16:37:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 193 ms / 2,000 ms |
コード長 | 1,109 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 108,464 KB |
最終ジャッジ日時 | 2024-10-12 16:37:49 |
合計ジャッジ時間 | 9,873 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
def factorization(n): arr = [] temp = n i=2 while i*i<=n: if i>2*10**5: break if temp%i==0: cnt=0 while temp%i==0: cnt+=1 temp //= i arr.append([i, cnt]) i+=1 if temp!=1: arr.append([temp, 1]) return arr edge=[] color=["b"] big = 0 X=int(input()) fac=factorization(X) if len(fac)==0: fac.append((1,1)) fac_ =[] for a,b in fac: if a==2: if b>=2: fac_.append((4,b//2)) if b%2!=0: fac_.append((2,b%2)) else: fac_.append((a,b)) fac = fac_ left=0 for a,b in fac: for _ in range(b): big+=1 if big!=1: edge.append((left,big)) color.append("b") if big>2*10**5: print(-1) exit(0) left=big for i in range(a): big+=1 edge.append((left,big)) color.append("g") if big>2*10**5: print(-1) exit(0) print(big) for u,v in edge: print(u, v) print(*color)