結果

問題 No.2929 Miracle Branch
コンテスト
ユーザー urunea
提出日時 2026-11-11 19:06:54
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 147 ms / 2,000 ms
+ 616µs
コード長 1,284 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 82 ms
コンパイル使用メモリ 64,952 KB
実行使用メモリ 92,440 KB
最終ジャッジ日時 2026-11-11 19:07:06
合計ジャッジ時間 11,672 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import Counter

X = int(input())
if X == 1:
    print(2)
    print(1, 2)
    print("b", "g")
    exit()
def sieve_of_eratosthenes(n):
    if n < 2:
        return []

    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False

    primes = [i for i, flag in enumerate(is_prime) if flag]

    return primes


prime_list = sieve_of_eratosthenes(3*10**5)
p = []
for i in prime_list:
    while X%i == 0:
        X //= i
        p.append(i)

if X >= 3*10**5:
    print(-1)
    exit()

C = Counter(p)
Cc = {}
for k, v in C.items():
    if k == 2:
        Cc[2] = 1 if v%2 == 1 else 0
        Cc[4] = v//2
    else:
        Cc[k] = v
cnt = 1
edge = []
color = []
num = 0
ans = 0
brown = []
for k, v in Cc.items():
    for _ in range(v):
        brown.append(cnt)
        color.append("b")
        cnt += 1
        for _ in range(k):
            color.append("g")
            edge.append([brown[-1], cnt])
            cnt += 1

for i in range(1, len(brown)):
    edge.append([brown[i-1], brown[i]])

if len(edge) + 1 > 2*10**5:
    print(-1)
    exit()

print(len(edge)+1)
for i, j in edge:
    print(i, j)
print(*color)
0