結果

問題 No.1711 Divide LCM
ユーザー LyricalMaestroLyricalMaestro
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 39 ms
53,536 KB
testcase_02 AC 40 ms
53,316 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 519 ms
127,628 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 109 ms
77,028 KB
testcase_41 AC 100 ms
76,936 KB
testcase_42 AC 96 ms
76,936 KB
testcase_43 AC 100 ms
76,992 KB
testcase_44 AC 97 ms
76,808 KB
権限があれば一括ダウンロードができます

ソースコード

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