結果
問題 | No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩 |
ユーザー |
![]() |
提出日時 | 2023-12-01 02:04:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 904 ms / 2,000 ms |
コード長 | 2,617 bytes |
コンパイル時間 | 489 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 149,620 KB |
最終ジャッジ日時 | 2024-09-26 15:05:55 |
合計ジャッジ時間 | 25,151 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 74 |
ソースコード
import sysreadline=sys.stdin.readlineimport bisectdef Bisect_Int(ok,ng,is_ok):while abs(ok-ng)>1:mid=(ok+ng)//2if is_ok(mid):ok=midelse:ng=midreturn okK,L,M,N,S=map(int,readline().split())A=list(map(int,readline().split()))B=list(map(int,readline().split()))C=list(map(int,readline().split()))D=list(map(int,readline().split()))plus0,minus0,zero0=[],[],0for a in A:for b in B:if a*b>0:plus0.append(a*b)elif a*b<0:minus0.append(-a*b)else:zero0+=1plus1,minus1,zero1=[],[],0for c in C:for d in D:if c*d>0:plus1.append(c*d)elif c*d<0:minus1.append(-c*d)else:zero1+=1minus0.sort()minus1.sort()plus0.sort()plus1.sort()def is_ok(ans):cnt=0if ans<0:i=len(plus1)for ab in minus0:while i and plus1[i-1]*ab>-ans:i-=1cnt+=len(plus1)-ii=len(minus1)for ab in plus0:while i and minus1[i-1]*ab>-ans:i-=1cnt+=len(minus1)-ielif ans==0:cnt+=len(plus0)*len(minus1)cnt+=len(plus1)*len(minus0)else:cnt+=len(plus0)*len(minus1)cnt+=len(plus1)*len(minus0)cnt+=zero0*(len(plus1)+len(minus1))+zero1*(len(plus0)+len(minus0))+zero0*zero1i=len(minus1)for ab in minus0:while i and minus1[i-1]*ab>=ans:i-=1cnt+=ii=len(plus1)for ab in plus0:while i and plus1[i-1]*ab>=ans:i-=1cnt+=ireturn cnt<Sinf=1<<60ans=Bisect_Int(-inf,inf,is_ok)if ans==0:for kk in range(K):if A[kk]==0:k,l,m,n=kk,0,0,0breakelse:for ll in range(L):if B[ll]==0:k,l,m,n=0,ll,0,0breakelse:for mm in range(M):if C[mm]==0:k,l,m,n=0,0,mm,0breakelse:for nn in range(N):if D[nn]==0:k,l,m,n=0,0,0,nnelse:dct={}for k in range(K):for l in range(L):dct[A[k]*B[l]]=(k,l)for m in range(M):for n in range(N):cd=C[m]*D[n]if cd and ans%cd==0 and ans//cd in dct:k,l=dct[ans//cd]breakelse:continuebreakprint(ans)print(" ".join(map(str,(A[k],B[l],C[m],D[n]))))