結果
問題 | No.2929 Miracle Branch |
ユーザー |
![]() |
提出日時 | 2024-06-15 10:25:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 210 ms / 2,000 ms |
コード長 | 1,032 bytes |
コンパイル時間 | 544 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 108,388 KB |
最終ジャッジ日時 | 2024-08-25 23:41:44 |
合計ジャッジ時間 | 10,653 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
def factorization(n):arr = []temp = nfor i in range(2, min(int(n**(1/2)+5), 2*10**5)):if temp%i==0:cnt=0while temp%i==0:cnt+=1temp //= iarr.append([i, cnt])if temp!=1:arr.append([temp, 1])if arr==[]:arr.append([n, 1])return arrn = int(input())F = factorization(n)A = []for i in range(len(F)):if(F[i][0] == 2):for _ in range(F[i][1] // 2):A.append(4)for _ in range(F[i][1] % 2):A.append(2)else:for _ in range(F[i][1]):A.append(F[i][0])cnt = len(A) + sum(A)if(cnt > 2*10**5):print(-1)exit()E = []C = [-1] * cntpu = -1v = 0for i in range(len(A)):u = vC[u] = "b"if(pu != -1):E.append([pu+1, u+1])pu = ufor _ in range(A[i]):v += 1E.append([u+1, v+1])C[v] = "g"v += 1print(cnt)for e in E:print(*e)print(*C)