結果
| 問題 | No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩 |
| コンテスト | |
| ユーザー |
 mkawa2
|
| 提出日時 | 2021-01-23 11:36:44 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,349 bytes |
| 記録 | |
| コンパイル時間 | 477 ms |
| コンパイル使用メモリ | 82,236 KB |
| 実行使用メモリ | 250,560 KB |
| 最終ジャッジ日時 | 2024-12-30 10:49:27 |
| 合計ジャッジ時間 | 78,884 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 56 TLE * 18 |
ソースコード
import sys
sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.buffer.readline())
def MI(): return map(int, sys.stdin.buffer.readline().split())
def MI1(): return map(int1, sys.stdin.buffer.readline().split())
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def LI1(): return list(map(int1, sys.stdin.buffer.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def BI(): return sys.stdin.buffer.readline().rstrip()
def SI(): return sys.stdin.buffer.readline().rstrip().decode()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
inf = 10**19
# md = 998244353
md = 10**9+7
def mulall(aa, bb):
pos = []
neg = []
zero = 0
for i, a in enumerate(aa):
for j, b in enumerate(bb):
if a*b == 0: zero += 1
elif a*b > 0: pos.append((a*b, i, j))
else: neg.append((a*b, i, j))
pos.sort(key=lambda x: x[0])
neg.sort(key=lambda x: x[0])
return pos, neg, zero
def ok1(m):
cnt = 0
if abp and cdn:
idx = len(cdn)-1
for x, i, j in abp[::-1]:
while idx >= 0 and cdn[idx][0]*x >= m:
idx -= 1
if idx < 0: break
cnt += idx+1
if abn and cdp:
idx = len(abn)-1
for x, i, j in cdp[::-1]:
while idx >= 0 and abn[idx][0]*x >= m:
idx -= 1
if idx < 0: break
cnt += idx+1
return cnt < s
def ok2(m):
cnt = 0
if abp and cdp:
idx = len(cdp)-1
for x, i, j in abp:
while idx >= 0 and cdp[idx][0]*x >= m:
idx -= 1
if idx < 0: break
cnt += idx+1
if abn and cdn:
idx = 0
for x, i, j in abn[::-1]:
while idx < len(cdn) and cdn[idx][0]*x >= m:
idx += 1
if idx >= len(cdn): break
cnt += len(cdn)-idx
return cnt < s
def findindex1(l):
if abp and cdn:
idx = 0
for x, i, j in abp:
while idx < len(cdn) and x*cdn[idx][0] < l:
idx += 1
if idx == len(cdn): break
if x*cdn[idx][0] == l:
print(aa[i], bb[j], cc[cdn[idx][1]], dd[cdn[idx][2]])
return
if abn and cdp:
idx = 0
for x, i, j in cdp:
while idx < len(abn) and x*abn[idx][0] < l:
idx += 1
if idx == len(abn): break
if x*abn[idx][0] == l:
print(aa[abn[idx][1]], bb[abn[idx][2]], cc[i], dd[j])
return
def findindex2(l):
if abp and cdp:
idx = len(cdp)-1
for x, i, j in abp:
while idx >= 0 and x*cdp[idx][0] > l:
idx -= 1
if idx < 0: break
if x*cdp[idx][0] == l:
print(aa[i], bb[j], cc[cdp[idx][1]], dd[cdp[idx][2]])
return
idx = len(cdn)-1
for x, i, j in abn:
while idx >= 0 and x*cdn[idx][0] < l:
idx -= 1
if idx < 0: break
if x*cdn[idx][0] == l:
print(aa[i], bb[j], cc[cdn[idx][1]], dd[cdn[idx][2]])
return
def find0(aa):
for i, a in enumerate(aa):
if a == 0: return i
return -1
an, bn, cn, dn, s = MI()
aa = LI()
bb = LI()
cc = LI()
dd = LI()
abp, abn, abz = mulall(aa, bb)
cdp, cdn, cdz = mulall(cc, dd)
# print(abp, abn, cdp, cdn)
if len(abp)*len(cdn)+len(abn)*len(cdp) >= s:
l = -10**18
r = 0
while l+1 < r:
m = (l+r)//2
if ok1(m): l = m
else: r = m
print(l)
findindex1(l)
elif len(abp)*len(cdn)+len(abn)*len(cdp)+abz*cn*dn+cdz*an*bn >= s:
print(0)
if abz:
i = find0(aa)
if i != -1:
print(0, bb[0], cc[0], dd[0])
exit()
i = find0(bb)
if i != -1:
print(aa[0], 0, cc[0], dd[0])
exit()
else:
i = find0(cc)
if i != -1:
print(aa[0], bb[0], 0, dd[0])
exit()
i = find0(dd)
if i != -1:
print(aa[0], bb[0], cc[0], 0)
exit()
else:
s -= len(abp)*len(cdn)+len(abn)*len(cdp)+abz*cn*dn+cdz*an*bn
l = 0
r = 10**18
while l+1 < r:
m = (l+r)//2
if ok2(m): l = m
else: r = m
print(l)
findindex2(l)