結果

問題 No.2244 Integer Complete
ユーザー gew1fw
提出日時 2025-06-12 19:17:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,162 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 82,080 KB
実行使用メモリ 75,980 KB
最終ジャッジ日時 2025-06-12 19:18:05
合計ジャッジ時間 5,034 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def merge_intervals(cards):
    intervals = []
    for a in cards:
        start = a * a
        end = (a + 1) * (a + 1) - 1
        if intervals and intervals[-1][1] >= start - 1:
            prev_start, prev_end = intervals.pop()
            new_start = prev_start
            new_end = max(prev_end, end)
            intervals.append((new_start, new_end))
        else:
            intervals.append((start, end))
    return intervals

def is_in_intervals(x, intervals):
    starts = [interval[0] for interval in intervals]
    idx = bisect.bisect_right(starts, x) - 1
    if idx >= 0:
        s, e = intervals[idx]
        if s <= x <= e:
            return True
    return False

def find_min_non_representable(A_intervals, B_intervals):
    max_A = max(end for start, end in A_intervals)
    max_B = max(end for start, end in B_intervals)
    min_A = A_intervals[0][0]
    min_B = B_intervals[0][0]
    min_product = min_A * min_B
    if min_product > 1:
        if not is_in_intervals(1, A_intervals) or not is_in_intervals(1, B_intervals):
            return 1
    
    k = 1
    while True:
        found = False
        divisors = set()
        sqrt_k = int(k ** 0.5)
        for i in range(1, sqrt_k + 1):
            if k % i == 0:
                d1 = i
                d2 = k // i
                if d1 <= max_A and d2 <= max_B:
                    divisors.add(d1)
                if d2 <= max_A and d1 <= max_B and d1 != d2:
                    divisors.add(d2)
        for d in divisors:
            if is_in_intervals(d, A_intervals) and is_in_intervals(k // d, B_intervals):
                found = True
                break
        if not found:
            return k
        k += 1

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    B = list(map(int, input[ptr:ptr+M]))
    ptr += M
    
    A_intervals = merge_intervals(A)
    B_intervals = merge_intervals(B)
    
    print(find_min_non_representable(A_intervals, B_intervals))

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