#1163104 (C++17) No.3527 Minimum Abs Sum

• 問題: No.3527 Minimum Abs Sum
• ユーザー: tnakao0123
• 提出日時: 2026-05-05 14:49:05
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 86 ms / 2,000 ms
• コード長: 3,324 bytes
• コンパイル時間: 721 ms
• コンパイル使用メモリ: 61,504 KB
• 実行使用メモリ: 10,112 KB
• 最終ジャッジ日時: 2026-05-05 14:49:18
• 合計ジャッジ時間: 3,024 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 30

ソースコード

/* -*- coding: utf-8 -*-
 *
 * 3527.cc:  No.3527 Minimum Abs Sum - yukicoder
 */

#include<cstdio>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_N = 200000;
const int MOD = 1000000007;
const __int128_t L4INF = (__int128_t)1 << 90;

/* typedef */

using ll = long long;
using l4 = __int128_t;

template<const int MOD>
struct MI {
  int v;
  MI(): v() {}
  MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; }
  MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; }

  explicit operator int() const { return v; }
  
  MI operator+(const MI m) const { return MI(v + m.v); }
  MI operator-(const MI m) const { return MI(v + MOD - m.v); }
  MI operator-() const { return MI(MOD - v); }
  MI operator*(const MI m) const { return MI((long long)v * m.v); }

  MI &operator+=(const MI m) { return (*this = *this + m); }
  MI &operator-=(const MI m) { return (*this = *this - m); }
  MI &operator*=(const MI m) { return (*this = *this * m); }

  bool operator==(const MI m) const { return v == m.v; }
  bool operator!=(const MI m) const { return v != m.v; }

  MI pow(int n) const {  // a^n % MOD
    MI pm = 1, a = *this;
    while (n > 0) {
      if (n & 1) pm *= a;
      a *= a;
      n >>= 1;
    }
    return pm;
  }

  MI inv() const { return pow(MOD - 2); }
  MI operator/(const MI m) const { return *this * m.inv(); }
  MI &operator/=(const MI m) { return (*this = *this / m); }
};

using mi = MI<MOD>;

template <typename T>
struct Frac {
  T n, d;
  Frac(): n(0), d(1) {}
  Frac(T _n): n(_n), d(1) {}
  Frac(T _n, T _d): n(_n), d(_d) { reduce(); }

  T __gcd(T m, T n) {  // m >= 0, n >= 0
    if (m < n) swap(m, n);
    while (n > 0) {
      T r = m % n;
      m = n;
      n = r;
    }
    return m;
  }

  void reduce() {
    if (d == 0) n = 0;
    else if (n == 0) d = 1;
    else {
      if (d < 0) n = -n, d = -d;
      T absn = (n >= 0) ? n : -n;
      T g = __gcd(absn, d);
      if (g > 1) n /= g, d /= g;
    }
  }

  bool operator<(const Frac &f) const { return n * f.d < f.n * d; }
  bool operator>(const Frac &f) const { return n * f.d > f.n * d; }
  bool operator==(const Frac &f) const { return n * f.d == f.n * d; }
  bool operator!=(const Frac &f) const { return n * f.d != f.n * d; }
};

using pfi = pair<Frac<ll>,int>;

/* global variables */

int as[MAX_N], bs[MAX_N];
pfi fis[MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", as + i);
  for (int i = 0; i < n; i++) scanf("%d", bs + i);

  int m = 0;
  ll sa = 0, sb = 0;
  for (int i = 0; i < n; i++) {
    if (as[i] > 0) as[i] = -as[i], bs[i] = -bs[i];
    if (as[i] != 0) {
      fis[m++] = {Frac<ll>(bs[i], as[i]), i};
      sa += as[i], sb += bs[i];
    }
  }
  sort(fis, fis + m);

  Frac<l4> miny(L4INF, 1);
  Frac<ll> minx;
  for (int i = 0; i < m; i++) {
    auto [xj, j] = fis[i];
    //printf(" %d/%d, %d,%d\n", xj.n, xj.d, as[j], bs[j]);

    sa -= as[j] * 2, sb -= bs[j] * 2;
    
    ll xn = xj.n, xd = xj.d;
    // y = f(x) = sa*x-sb = sa*xn/xd-sb = (sa*xn-sb*xd)/xd
    Frac<l4> y((l4)sa * xn - (l4)sb * xd, xd);
    //printf(" i=%d: x=%lld/%lld, y=%lld/%lld\n", i, xj.n, xj.d, (ll)y.n, (ll)y.d);
    if (miny > y) miny = y, minx = xj;
  }

  mi ans = mi(minx.n) / mi(minx.d);
  printf("%d\n", (int)ans);
  
  return 0;
}