提出 #15050255

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define rep(i, x) for (ll i = 0; i < (x); i++)
#define chmax(x, a)  do { x = max(x, a); } while(0)

template<typename T>
using reversed_priority_queue = \
    std::priority_queue<T, std::vector<T>, std::greater<T> >;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
// {{{ Modint
// using mint = modint<1000000007>;
// mint x = 2;
// mint y = mint::P(5, 2);
// std::cout << x.a << std::endl;
template <std::int64_t M>
class modint {
 public:
  int64_t a;
  static std::vector<modint> fact;
  static std::vector<modint> inv_fact;
  explicit constexpr modint(const int64_t x = 0) noexcept :
    a((x % M + M) % M) {}
  constexpr int64_t &value() noexcept { return a; }
  constexpr const int64_t &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= M) {
      a -= M;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += M;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % M;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    int64_t exp = M - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  constexpr modint pow(ll t) const {
    if (!t) return modint(1);
    modint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  static modint P(ll n, ll k) {
    if (fact.size() == 0) {
      const ll T = 3000000;
      fact.resize(T, modint(1));
      inv_fact.resize(T, modint(1));
      for (ll i = 2; i < T; i++) fact[i] = fact[i-1] * modint(i);
      for (ll i = 2; i < T; i++) inv_fact[i] = inv_fact[i-1] / modint(i);
    }
    if (n < k) return modint(0);
    if (n < 0 || k < 0) return modint(0);
    return fact[n] * inv_fact[n - k];
  }

  static modint C(ll n, ll k) {
    if (n < k) return modint(0);
    if (n < 0 || k < 0) return modint(0);
    return P(n, k) * inv_fact[k];
  }
};
template <std::int64_t M>
std::vector<modint<M>> modint<M>::fact;
template <std::int64_t M>
std::vector<modint<M>> modint<M>::inv_fact;
// }}}
using mint = modint<1000000007>;

int main(void) {
  ll N, K;
  cin >> N >> K;

  deque<ll> a;  // 非負数を降順 9 6 5 ...
  deque<ll> b;  // 負数を昇順 -8 -7 -3 ...
  deque<ll> c;  // すべての要素
  {
    vector<ll> av;
    vector<ll> bv;
    vector<ll> cv;
    rep(i, N) {
      ll x;
      cin >> x;
      if (x >= 0) av.push_back(x);
      else bv.push_back(x);
      cv.push_back(x);
    }
    sort(begin(av), end(av), greater<ll>());
    sort(begin(bv), end(bv));
    sort(begin(cv), end(cv), [](const ll l, const ll r) {
        if (abs(l) == abs(r))
          return l > r;
        else
          return abs(l) < abs(r);
        });
    
    rep(i, av.size()) a.push_back(av[i]);
    rep(i, bv.size()) b.push_back(bv[i]);
    rep(i, cv.size()) c.push_back(cv[i]);
  }

  // 答えが負数になる場合
  mint ans_min(1);
  rep(i, K)
    ans_min *= mint(c[i]);

  // 答えが正数になる場合
  mint ans(1);
  while(K >= 2 && a.size() >= 2 && b.size() >= 2) {
    ll av = a[0] * a[1];
    ll bv = b[0] * b[1];
    if (av > bv) {
      ans *= mint(a[0]);  // 1個だけ取るのが肝！
      a.erase(a.begin());
      K--;
    } else {
      ans *= mint(b[0]) * mint(b[1]);
      b.erase(b.begin());
      b.erase(b.begin());
      K-=2;
    }
  }

  if (K >= 2) {
    if (a.size() <= 1) {
      while (K >= 2 && b.size() >= 2) {
        ans *= mint(b[0]) * mint(b[1]);
        b.erase(b.begin());
        b.erase(b.begin());
        K-=2;
      }
    } else { // b.size() <= 1
      while (K > 0 && a.size() > 0) {
        ans *= mint(a[0]);
        a.erase(a.begin());
        K--;
      }
    }
  }


  if (K == 0) {
    cout << ans.value() << endl;
    return 0;
  }

  if (K == 1) {
    if (a.size() > 0) {
      ans *= mint(a[0]);
    } else { // b.size() > 0
      ans = ans_min;
    }
    cout << ans.value() << endl;
    K--;
    return 0;
  }
  return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:2:36: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    2 | #define rep(i, x) for (ll i = 0; i < (x); i++)
      |                                    ^
./Main.cpp:127:5: note: in expansion of macro ‘rep’
  127 |     rep(i, av.size()) a.push_back(av[i]);
      |     ^~~
./Main.cpp:2:36: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    2 | #define rep(i, x) for (ll i = 0; i < (x); i++)
      |                                    ^
./Main.cpp:128:5: note: in expansion of macro ‘rep’
  128 |     rep(i, bv.size()) b.push_back(bv[i]);
      |     ^~~
./Main.cpp:2:36: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    2 | #define rep(i, x) for (ll i = 0; i < (x); i++)
      |                                    ^
./Main.cpp:129:5: note: in expansion of macro ‘rep’
  129 |     rep(i, cv.size()) c.push_back(cv[i]);
      |     ^~~

ジャッジ結果