結果

問題 No.12 限定された素数
ユーザー lam6er
提出日時 2025-03-26 15:50:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 916 ms / 5,000 ms
コード長 1,809 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 240,052 KB
最終ジャッジ日時 2025-03-26 15:50:52
合計ジャッジ時間 23,909 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left, bisect_right

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    A = input[idx:idx+N]
    s_set = set(A)
    sieve_limit = 5000000
    primes = []
    sieve = [True] * (sieve_limit + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(sieve_limit**0.5) + 1):
        if sieve[i]:
            sieve[i*i::i] = [False] * len(sieve[i*i::i])
    for i in range(sieve_limit + 1):
        if sieve[i]:
            primes.append(i)
    
    valid_primes = []
    invalid_primes = []
    for p in primes:
        p_str = str(p)
        valid = True
        for c in p_str:
            if c not in s_set:
                valid = False
                break
        if valid:
            valid_primes.append(p)
        else:
            invalid_primes.append(p)
    
    invalid_primes = [0] + invalid_primes + [5000001]
    valid_primes.sort()
    s = set(s_set)
    max_diff = -1
    
    for i in range(len(invalid_primes) - 1):
        prev = invalid_primes[i]
        next_ = invalid_primes[i+1]
        a = prev + 1
        b = next_ - 1
        if a > b:
            continue
        
        left = bisect_left(valid_primes, a)
        right = bisect_right(valid_primes, b)
        primes_in_range = valid_primes[left:right]
        if not primes_in_range:
            continue
        
        current_digits = set()
        for p in primes_in_range:
            current_digits.update(str(p))
            if len(current_digits) == len(s):
                break
        
        if current_digits == s:
            current_diff = b - a
            if current_diff > max_diff:
                max_diff = current_diff
    
    print(max_diff if max_diff != -1 else -1)

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