結果

問題 No.3527 Minimum Abs Sum
コンテスト
ユーザー miya145592
提出日時 2026-05-04 23:46:27
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 3,393 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 172 ms
コンパイル使用メモリ 85,216 KB
実行使用メモリ 151,500 KB
最終ジャッジ日時 2026-05-04 23:46:46
合計ジャッジ時間 15,682 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from functools import cmp_to_key
import sys
input = sys.stdin.readline
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
M = []
P = []
Z = []
for i in range(N):
    if A[i]>0:
        P.append((A[i], B[i]))
    elif A[i]<0:
        M.append((A[i], B[i]))
    else:
        Z.append((A[i], B[i]))

def cmp(a, b):
    if (a[0]<0 and a[1]<0) or (a[0]>=0 and a[1]>=0):
        asign = 1
    else:
        asign = -1
    if (b[0]<0 and b[1]<0) or (b[0]>=0 and b[1]>=0):
        bsign = 1
    else:
        bsign = -1
    if asign<bsign:
        return -1
    elif asign>bsign:
        return 1
    if asign==1:
        if a[0]*b[1]<a[1]*b[0]:
            return -1
        elif a[0]*b[1]>a[1]*b[0]:
            return 1
        else:
            return 0
    else:
        if a[0]*b[1]<a[1]*b[0]:
            return 1
        elif a[0]*b[1]>a[1]*b[0]:
            return -1
        else:
            return 0
   
P.sort(key=cmp_to_key(cmp))
M.sort(key=cmp_to_key(cmp))
PA = [0]
PB = [0]
for a, b in P:
    PA.append(PA[-1]+a)
    PB.append(PB[-1]+b)
MA = [0]
MB = [0]
for a, b in M:
    MA.append(MA[-1]+a)
    MB.append(MB[-1]+b)
SZ = 0
for a, b in Z:
    SZ += abs(b)
INF = 10**18
ans = (INF, 1)
ans2 = (INF, 1)
i = 0
j = 0
while i<len(P) or j<len(M):
    if i<len(P) and j<len(M):
        pa, pb = P[i]
        ma, mb = M[j]
        if cmp((P[i][1], P[i][0]), (M[j][1], M[j][0]))<0:
            tmp = SZ
            tmp += (PB[-1]-PB[i])*pa - (PA[-1]-PA[i]) * pb
            tmp += (PA[i] * pb) - PB[i]*pa
            tmp += MB[j]*pa - MA[j] * pb
            tmp += (MA[-1]-MA[j]) * pb - (MB[-1]-MB[j]) * pa
            if cmp((tmp, pa), ans)<0:
                ans = (tmp, pa)
                ans2 = (P[i][1], P[i][0])
            elif cmp((tmp, pa), ans)==0 and cmp((P[i][1], P[i][0]), ans2)<0 :
                ans2 = (P[i][1], P[i][0])
            i+=1
        else:
            tmp = SZ
            tmp += (PB[-1]-PB[i])*ma - (PA[-1]-PA[i]) * mb
            tmp += (PA[i] * mb) - PB[i]*ma
            tmp += MB[j]*ma - MA[j] * mb
            tmp += (MA[-1]-MA[j]) * mb - (MB[-1]-MB[j])*ma
            if cmp((tmp, ma), ans)<0:
                ans = (tmp, ma)
                ans2 = (M[j][1], M[j][0])
            elif cmp((tmp, ma), ans)==0 and cmp((M[j][1], M[j][0]), ans2)<0:
                ans2 = (M[j][1], M[j][0])
            j+=1
    elif i<len(P):
        pa, pb = P[i]
        tmp = SZ
        tmp += (PB[-1]-PB[i])*pa - (PA[-1]-PA[i]) * pb
        tmp += (PA[i] * pb) - PB[i]*pa
        tmp += MB[j]*pa - MA[j] * pb
        tmp += (MA[-1]-MA[j]) * pb - (MB[-1]-MB[j]) * pa
        if cmp((tmp, pa), ans)<0:
            ans = (tmp, pa)
            ans2 = (P[i][1], P[i][0])
        elif cmp((tmp, pa), ans)==0 and cmp((P[i][1], P[i][0]), ans2)<0 :
            ans2 = (P[i][1], P[i][0])
        i+=1
    else:
        ma, mb = M[j]
        tmp = SZ
        tmp += (PB[-1]-PB[i])*ma - (PA[-1]-PA[i]) * mb
        tmp += (PA[i] * mb) - PB[i]*ma
        tmp += MB[j]*ma - MA[j] * mb
        tmp += (MA[-1]-MA[j]) * mb - (MB[-1]-MB[j])*ma
        if cmp((tmp, ma), ans)<0:
            ans = (tmp, ma)
            ans2 = (M[j][1], M[j][0])
        elif cmp((tmp, ma), ans)==0 and cmp((M[j][1], M[j][0]), ans2)<0:
            ans2 = (M[j][1], M[j][0])
        j+=1

ans3 = ans2[0] * pow(ans2[1], MOD-2, MOD) % MOD
print(ans3)
0