結果

問題 No.2244 Integer Complete
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:16:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,443 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 354 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 97,376 KB
最終ジャッジ日時 2025-06-12 19:16:29
合計ジャッジ時間 5,189 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math

def preprocess_intervals(arr):
    intervals = []
    for a in arr:
        s = a * a
        e = (a + 1) * (a + 1) - 1
        intervals.append((s, e))
    return intervals

def is_in(number, intervals):
    left = 0
    right = len(intervals) - 1
    res = -1
    while left <= right:
        mid = (left + right) // 2
        s, e = intervals[mid]
        if s <= number:
            res = mid
            left = mid + 1
        else:
            right = mid - 1
    if res == -1:
        return False
    return number <= intervals[res][1]

def find_min_missing(X_intervals, Y_intervals):
    k = 1
    while True:
        found = False
        max_d = int(math.isqrt(k))
        for d in range(1, max_d + 1):
            if k % d == 0:
                e = k // d
                if (is_in(d, X_intervals) and is_in(e, Y_intervals)) or (is_in(e, X_intervals) and is_in(d, Y_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]))
    X_intervals = preprocess_intervals(A)
    Y_intervals = preprocess_intervals(B)
    print(find_min_missing(X_intervals, Y_intervals))

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