結果

問題 No.1711 Divide LCM
コンテスト
ユーザー LyricalMaestro
提出日時 2024-12-15 03:02:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,236 bytes
コンパイル時間 392 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 138,724 KB
最終ジャッジ日時 2024-12-15 03:03:06
合計ジャッジ時間 22,386 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 6 WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1711

def calc_s(primes, i):
    ans = 1
    for p, e in primes[i].items():
        ans *= pow(p, e)
    return str(ans)



def main():
    N = int(input())
    primes = []
    for _ in range(N):
        m = int(input())
        p_map = {}
        for _ in range(m):
            p, e = map(int ,input().split())
            p_map[p] = e
        primes.append(p_map)
    
    # LCM(S)を計算
    all_primes = {}
    for i, p_map in enumerate(primes):
        for p, e in p_map.items():
            if p not in all_primes:
                all_primes[p] = [-1, []]
            if all_primes[p][0] < e:
                all_primes[p][0] = e
                all_primes[p][1].clear()
                all_primes[p][1].append(i)
            elif all_primes[p][0] == e:
                all_primes[p][1].append(i)
    
    # LCM(Si) = LCM(S)となるiが存在するか?
    for p_map in primes:
        if len(p_map) < len(all_primes):
            continue

        not_is_max = False
        for p, e in p_map.items():
            if e < all_primes[p][0]:
                not_is_max = True
        if not not_is_max:
            print(-1)
            return
        
    # k = 2, 3なのでk=2ができるかをベースにけんとうする
    for p, v_array  in all_primes.items():
        p_set = {p}
        for i0 in v_array[1]:
            for p, e in primes[i0].items():
                if all_primes[p][0] == e:
                    p_set.add(p)
        
        if len(p_set) != len(all_primes):
            print(2)
            v_flg = [0] * N
            for j in v_array[1]:
                v_flg[j] = 1
            ans_array1 = [len(v_array)]
            ans_array2 = [N - len(v_array)]
            for j in range(N):
                if v_flg[j]:
                    ans_array1.append(calc_s(primes, j))
                else:
                    ans_array2.append(calc_s(primes, j))
            print(" ".join(map(str, ans_array1)))
            print(" ".join(map(str, ans_array2)))
            return
    
    # k = 3のパターン
    target_v_array = None
    for p, v_array  in all_primes.items():
        target_v_array = v_array
        break

    i0 = target_v_array[1][0]
    target_p = -1
    target_e = -1
    for p, e_array in all_primes.items():
        if p not in primes[i0] or primes[i0][p] < e_array[0]:
            target_p = p
            target_e = e_array[0]
            break

    i_set1 = set()
    i_set2 = set()
    for i in target_v_array[1]:
        if target_p not in primes[i] or primes[i][target_p] < target_e:
            i_set1.add(i)
        else:
            i_set2.add(i)

    i_set3 = set()
    for i in range(N):
        if i not in i_set1 and i not in i_set2:
            i_set3.add(i)
    
    print(3)
    i_array1 = [len(i_set1)]
    for s in i_set1:
        i_array1.append(calc_s(primes, s))
    i_array2 = [len(i_set2)]
    for s in i_set2:
        i_array2.append(calc_s(primes,s))
    i_array3 = [len(i_set3)]
    for s in i_set3:
        i_array3.append(calc_s(primes, s))
    print(" ".join(map(str, i_array1)))
    print(" ".join(map(str, i_array2)))
    print(" ".join(map(str, i_array3)))
    



    




if __name__ == "__main__":
    main()
0