結果

問題 No.2244 Integer Complete
ユーザー lam6er
提出日時 2025-03-20 20:20:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,565 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 97,804 KB
最終ジャッジ日時 2025-03-20 20:21:18
合計ジャッジ時間 5,044 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

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
    
    def generate_intervals(arr):
        intervals = []
        for num in arr:
            start = num * num
            end = (num +1) **2
            intervals.append( (start, end) )
        return intervals
    
    def merge_intervals(intervals):
        if not intervals:
            return []
        sorted_intervals = sorted(intervals, key=lambda x: x[0])
        merged = [ list(sorted_intervals[0]) ]
        for current in sorted_intervals[1:]:
            last = merged[-1]
            if current[0] <= last[1]:
                last[1] = max(last[1], current[1])
            else:
                merged.append( list(current) )
        return [ (interval[0], interval[1]) for interval in merged ]
    
    x_intervals = generate_intervals(A)
    y_intervals = generate_intervals(B)
    
    merged_x = merge_intervals(x_intervals)
    merged_y = merge_intervals(y_intervals)
    
    starts_x = [ interval[0] for interval in merged_x ]
    ends_x = [ interval[1] for interval in merged_x ]
    starts_y = [ interval[0] for interval in merged_y ]
    ends_y = [ interval[1] for interval in merged_y ]
    
    def is_in(num, starts, ends):
        left = 0
        right = len(starts) -1
        res = -1
        while left <= right:
            mid = (left + right) //2
            if starts[mid] <= num:
                res = mid
                left = mid +1
            else:
                right = mid -1
        if res == -1:
            return False
        return ends[res] > num
    
    def get_divisors(s):
        divisors = set()
        for i in range(1, int(math.isqrt(s)) +1):
            if s % i ==0:
                divisors.add(i)
                divisors.add(s//i)
        return divisors
    
    s = 1
    while True:
        divisors = get_divisors(s)
        found = False
        for d in divisors:
            # Check d is x, s/d is y
            if is_in(d, starts_x, ends_x) and is_in(s // d, starts_y, ends_y):
                found = True
                break
            # Check s/d is x, d is y
            if is_in(s // d, starts_x, ends_x) and is_in(d, starts_y, ends_y):
                found = True
                break
        if not found:
            print(s)
            return
        s +=1

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