結果

問題 No.3372 Suitable Constraint
コンテスト
ユーザー titia
提出日時 2025-11-21 21:47:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 327 ms / 2,000 ms
コード長 1,588 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 114,748 KB
最終ジャッジ日時 2025-11-21 21:47:16
合計ジャッジ時間 4,703 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
            
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)

T=int(input())

for tests in range(T):
    N=int(input())
    A=list(map(int,input().split()))

    A.sort()

    X=[]
    Y=[]
    Z=[]

    for a in A:
        if a>0:
            X.append(a)
        elif a<0:
            Y.append(a)
        else:
            Z.append(a)

    if X:
        if len(X)>=4:
            X=X[:2]+X[-2:]
    if Y:
        if len(Y)>=4:
            Y=Y[:2]+Y[-2:]
    if Z:
        if len(Z)>=2:
            Z=[0,0]

    A=X+Y+Z

    n=len(A)

    ANS=-1<<60

    SET=set()

    for i in range(len(A)):
        for j in range(i+1,len(A)):
            X=A[i]*A[j]
            SET.add(X)

    SET=sorted(SET)

    OK=0
    NG=len(SET)

    while NG>OK+1:
        mid=(OK+NG)//2

        X=SET[mid]
        #print(X)

        Group = [i for i in range(n)] # グループ分け
        Nodes = [1]*(n) # 各グループのノードの数

        for k in range(len(A)):
            for l in range(k+1,len(A)):
                if A[k]*A[l]>=X:
                    Union(k,l)

        if Nodes[find(0)]==len(A):
            OK=mid
        else:
            NG=mid

    print(SET[OK])
0