#1164050 (PyPy3) No.3527 Minimum Abs Sum

• 問題: No.3527 Minimum Abs Sum
• ユーザー: 回転
• 提出日時: 2026-05-09 02:27:28
• 言語: PyPy3 (7.3.17)
• 結果: TLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 5,657 bytes
• コンパイル時間: 255 ms
• コンパイル使用メモリ: 85,120 KB
• 実行使用メモリ: 138,312 KB
• 最終ジャッジ日時: 2026-05-09 06:05:35
• 合計ジャッジ時間: 28,506 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

ファイルパターン	結果
sample	AC * 3
other	AC * 28 TLE * 2

ソースコード

import math

class Fraction:
    __slots__ = ('num', 'den')

    def __init__(self, numerator, denominator=1):
        if type(numerator) is Fraction and denominator == 1:
            self.num = numerator.num
            self.den = numerator.den
            return

        if denominator == 0:
            raise ZeroDivisionError("Fraction denominator cannot be zero")
        
        # math.gcd はC実装のため非常に高速
        g = math.gcd(numerator, denominator)
        if denominator < 0:
            g = -g
        
        self.num = numerator // g
        self.den = denominator // g

    @property
    def numerator(self):
        return self.num

    @property
    def denominator(self):
        return self.den

    def as_integer_ratio(self):
        """分子と分母のペアをタプルで返す"""
        return (self.num, self.den)

    def __add__(self, other):
        if type(other) is int:
            return Fraction(self.num + other * self.den, self.den)
        elif type(other) is Fraction:
            return Fraction(self.num * other.den + other.num * self.den, self.den * other.den)
        return NotImplemented

    def __radd__(self, other):
        return self.__add__(other)

    def __sub__(self, other):
        if type(other) is int:
            return Fraction(self.num - other * self.den, self.den)
        elif type(other) is Fraction:
            return Fraction(self.num * other.den - other.num * self.den, self.den * other.den)
        return NotImplemented

    def __rsub__(self, other):
        if type(other) is int:
            return Fraction(other * self.den - self.num, self.den)
        return NotImplemented

    def __mul__(self, other):
        if type(other) is int:
            return Fraction(self.num * other, self.den)
        elif type(other) is Fraction:
            return Fraction(self.num * other.num, self.den * other.den)
        return NotImplemented

    def __rmul__(self, other):
        return self.__mul__(other)

    def __truediv__(self, other):
        if type(other) is int:
            return Fraction(self.num, self.den * other)
        elif type(other) is Fraction:
            return Fraction(self.num * other.den, self.den * other.num)
        return NotImplemented

    def __rtruediv__(self, other):
        if type(other) is int:
            return Fraction(other * self.den, self.num)
        return NotImplemented
    
    def __floordiv__(self, other):
        return int(self.__truediv__(other))
    
    def __rfloordiv__(self, other):
        return int(self.__rtruediv__(other))
        
    def __mod__(self, other):
        div = self // other
        return self - other * div
        
    def __rmod__(self, other):
        div = other // self
        return other - self * div

    def __pow__(self, power):
        if type(power) is int:
            if power >= 0:
                return Fraction(self.num ** power, self.den ** power)
            else:
                return Fraction(self.den ** -power, self.num ** -power)
        return float(self) ** power

    def __neg__(self):
        return Fraction(-self.num, self.den)

    def __pos__(self):
        return self

    def __abs__(self):
        return Fraction(abs(self.num), self.den)

    def __eq__(self, other):
        if type(other) is int:
            return self.num == other and self.den == 1
        if type(other) is Fraction:
            return self.num == other.num and self.den == other.den
        if type(other) is float:
            return float(self) == other
        return NotImplemented

    def __lt__(self, other):
        if type(other) is int:
            return self.num < other * self.den
        if type(other) is Fraction:
            return self.num * other.den < other.num * self.den
        if type(other) is float:
            return float(self) < other
        return NotImplemented

    def __le__(self, other):
        if type(other) is int:
            return self.num <= other * self.den
        if type(other) is Fraction:
            return self.num * other.den <= other.num * self.den
        if type(other) is float:
            return float(self) <= other
        return NotImplemented

    def __gt__(self, other):
        if type(other) is int:
            return self.num > other * self.den
        if type(other) is Fraction:
            return self.num * other.den > other.num * self.den
        if type(other) is float:
            return float(self) > other
        return NotImplemented

    def __ge__(self, other):
        if type(other) is int:
            return self.num >= other * self.den
        if type(other) is Fraction:
            return self.num * other.den >= other.num * self.den
        if type(other) is float:
            return float(self) >= other
        return NotImplemented

    def __bool__(self):
        return self.num != 0

    def __int__(self):
        return self.num // self.den

    def __float__(self):
        return self.num / self.den

    def __hash__(self):
        return hash((self.num, self.den))

    def __str__(self):
        if self.den == 1:
            return str(self.num)
        return f"{self.num}/{self.den}"

    def __repr__(self):
        return f"Fraction({self.num}, {self.den})"
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
SUM = sum(abs(i) for i in A)

a = []
for i in range(N):
    if(A[i] == 0):continue
    a.append((Fraction(B[i],A[i]),abs(A[i])))
a.sort()

now = 0
for v,num in a:
    now += num
    if(now >= -(-SUM//2)):
        b,c = v.as_integer_ratio()
        print(b * pow(c,-1,MOD) % MOD)
        exit()