#1196863 (C++23(gcc16)) No.3527 Minimum Abs Sum

• 問題: No.3527 Minimum Abs Sum
• ユーザー: C
• 提出日時: 2026-11-04 16:02:17
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 36 ms / 2,000 ms
• コード長: 8,241 bytes
• コンパイル時間: 6,432 ms
• コンパイル使用メモリ: 392,848 KB
• 実行使用メモリ: 11,252 KB
• 最終ジャッジ日時: 2026-11-04 16:02:54
• 合計ジャッジ時間: 10,867 ms
• ジャッジサーバーID （参考情報）: judge7_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
// using namespace atcoder;
using ll=long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
using mint=atcoder::modint1000000007;
// using mint2=static_modint<2>;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

// using mint=LazyMontgomeryModInt<998244353>;
using vm=vector<mint>;
// using vvm=vector<vm>;

#line 2 "math/rational.hpp"

#include <cassert>
#include <numeric>
#include <vector>
using namespace std;

#line 2 "internal/internal-type-traits.hpp"

#include <type_traits>
using namespace std;

namespace internal {
template <typename T>
using is_broadly_integral =
    typename conditional_t<is_integral_v<T> || is_same_v<T, __int128_t> ||
                               is_same_v<T, __uint128_t>,
                           true_type, false_type>::type;

template <typename T>
using is_broadly_signed =
    typename conditional_t<is_signed_v<T> || is_same_v<T, __int128_t>,
                           true_type, false_type>::type;

template <typename T>
using is_broadly_unsigned =
    typename conditional_t<is_unsigned_v<T> || is_same_v<T, __uint128_t>,
                           true_type, false_type>::type;

#define ENABLE_VALUE(x) \
  template <typename T> \
  constexpr bool x##_v = x<T>::value;

ENABLE_VALUE(is_broadly_integral);
ENABLE_VALUE(is_broadly_signed);
ENABLE_VALUE(is_broadly_unsigned);
#undef ENABLE_VALUE

#define ENABLE_HAS_TYPE(var)                                   \
  template <class, class = void>                               \
  struct has_##var : false_type {};                            \
  template <class T>                                           \
  struct has_##var<T, void_t<typename T::var>> : true_type {}; \
  template <class T>                                           \
  constexpr auto has_##var##_v = has_##var<T>::value;

#define ENABLE_HAS_VAR(var)                                     \
  template <class, class = void>                                \
  struct has_##var : false_type {};                             \
  template <class T>                                            \
  struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \
  template <class T>                                            \
  constexpr auto has_##var##_v = has_##var<T>::value;

}  // namespace internal
#line 2 "math-fast/gcd.hpp"

#include <algorithm>
using namespace std;

namespace BinaryGCDImpl {
using u64 = unsigned long long;
using i8 = char;

u64 binary_gcd(u64 a, u64 b) {
  if (a == 0 || b == 0) return a + b;
  i8 n = __builtin_ctzll(a);
  i8 m = __builtin_ctzll(b);
  a >>= n;
  b >>= m;
  n = min(n, m);
  while (a != b) {
    u64 d = a - b;
    i8 s = __builtin_ctzll(d);
    bool f = a > b;
    b = f ? b : a;
    a = (f ? d : -d) >> s;
  }
  return a << n;
}

using u128 = __uint128_t;
// a > 0
int ctz128(u128 a) {
  u64 lo = a & u64(-1);
  return lo ? __builtin_ctzll(lo) : 64 + __builtin_ctzll(a >> 64);
}
u128 binary_gcd128(u128 a, u128 b) {
  if (a == 0 || b == 0) return a + b;
  i8 n = ctz128(a);
  i8 m = ctz128(b);
  a >>= n;
  b >>= m;
  n = min(n, m);
  while (a != b) {
    u128 d = a - b;
    i8 s = ctz128(d);
    bool f = a > b;
    b = f ? b : a;
    a = (f ? d : -d) >> s;
  }
  return a << n;
}

}  // namespace BinaryGCDImpl

long long binary_gcd(long long a, long long b) {
  return BinaryGCDImpl::binary_gcd(abs(a), abs(b));
}
__int128_t binary_gcd128(__int128_t a, __int128_t b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  return BinaryGCDImpl::binary_gcd128(a, b);
}

/**
 * @brief binary GCD
 */
#line 10 "math/rational.hpp"

// T : 値, U : 比較用
template <typename T, typename U>
struct RationalBase {
  using R = RationalBase;
  using Key = T;
  T x, y;
  RationalBase() : x(0), y(1) {}
  template <typename T1>
  RationalBase(const T1& _x) : RationalBase<T, U>(_x, T1{1}) {}
  template <typename T1, typename T2>
  RationalBase(const pair<T1, T2>& _p)
      : RationalBase<T, U>(_p.first, _p.second) {}
  template <typename T1, typename T2>
  RationalBase(const T1& _x, const T2& _y) : x(_x), y(_y) {
    assert(y != 0);
    if (y == -1) x = -x, y = -y;
    if (y != 1) {
      T g;
      if constexpr (internal::is_broadly_integral_v<T>) {
        if constexpr (sizeof(T) == 16) {
          g = binary_gcd128(x, y);
        } else {
          g = binary_gcd(x, y);
        }
      } else {
        g = gcd(x, y);
      }
      if (g != 0) x /= g, y /= g;
      if (y < 0) x = -x, y = -y;
    }
  }
  // y = 0 の代入も認める
  static R raw(T _x, T _y) {
    R r;
    r.x = _x, r.y = _y;
    return r;
  }
  friend R operator+(const R& l, const R& r) {
    if (l.y == r.y) return R{l.x + r.x, l.y};
    return R{l.x * r.y + l.y * r.x, l.y * r.y};
  }
  friend R operator-(const R& l, const R& r) {
    if (l.y == r.y) return R{l.x - r.x, l.y};
    return R{l.x * r.y - l.y * r.x, l.y * r.y};
  }
  friend R operator*(const R& l, const R& r) { return R{l.x * r.x, l.y * r.y}; }
  friend R operator/(const R& l, const R& r) { return R{l.x * r.y, l.y * r.x}; }
  R& operator+=(const R& r) { return (*this) = (*this) + r; }
  R& operator-=(const R& r) { return (*this) = (*this) - r; }
  R& operator*=(const R& r) { return (*this) = (*this) * r; }
  R& operator/=(const R& r) { return (*this) = (*this) / r; }
  R operator-() const { return raw(-x, y); }
  R inverse() const {
    assert(x != 0);
    R r = raw(y, x);
    if (r.y < 0) r.x = -r.x, r.y = -r.y;
    return r;
  }
  R pow(long long p) const {
    R res{1}, base{*this};
    while (p) {
      if (p & 1) res *= base;
      base *= base;
      p >>= 1;
    }
    return res;
  }
  friend bool operator==(const R& l, const R& r) {
    return l.x == r.x && l.y == r.y;
  };
  friend bool operator!=(const R& l, const R& r) {
    return l.x != r.x || l.y != r.y;
  };
  friend bool operator<(const R& l, const R& r) {
    return U{l.x} * r.y < U{l.y} * r.x;
  };
  friend bool operator<=(const R& l, const R& r) { return l < r || l == r; }
  friend bool operator>(const R& l, const R& r) {
    return U{l.x} * r.y > U{l.y} * r.x;
  };
  friend bool operator>=(const R& l, const R& r) { return l > r || l == r; }
  friend ostream& operator<<(ostream& os, const R& r) {
    os << r.x;
    if (r.x != 0 && r.y != 1) os << "/" << r.y;
    return os;
  }

  // T にキャストされるので T が bigint の場合は to_ll も要る
  T to_mint(T mod) const {
    assert(mod != 0);
    T a = y, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return U((u % mod + mod) % mod) * x % mod;
  }
};

using Rational = RationalBase<long long, __int128_t>;
using Fraction = Rational;

struct node{
	Rational t;
	ll w;
};

int main()
{
  	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//重み付き中央値という問題に帰着できます
	//再帰を使えばO(N)で解けます（線形選択アルゴリズムと大きく変わりません）
	int N;
	cin>>N;
	vll A(N);
	rep(i,0,N)cin>>A[i];
	vector<node>v;
	ll W=0;
	rep(i,0,N){
		ll b;
		cin>>b;
		if(A[i]==0)continue;
		ll w=abs(A[i]);
		v.push_back({Rational(b,A[i]),w});
		W+=w;
	}
	ll K=(W+1)/2;
	auto lo=v.begin(),hi=v.end();
	while(1){
		auto mid=lo+(hi-lo)/2;
		nth_element(lo,mid,hi,[](const auto&a,const auto& b){return a.t<b.t;});
		Rational p=mid->t;
		//[lo,m1): t_i < p
		//[m1,m2): t_i = p
		//[m2,hi): t_i > p
		auto m1=partition(lo,hi,[&](const auto&a){return a.t<p;});
		auto m2=partition(m1,hi,[&](const auto&a){return a.t==p;});
		ll L=0,E=0;
		for(auto it=lo;it!=m1;++it)L+=it->w;
		for(auto it=m1;it!=m2;++it)E+=it->w;
		if(K<=L){
			//左に再帰
			hi=m1;
		}else if(K<=L+E){
			//pが答え
			cout<<(mint(p.x)/mint(p.y)).val()<<'\n';
			return 0;
		}else{
			//右に再帰
			K-=L+E;
			lo=m2;
		}
	}

}