Submission #15050255


Source Code Expand

Copy
#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;
}

Submission Info

Submission Time
Task E - Multiplication 4
User bobuhiro11
Language C++ (GCC 9.2.1)
Score 500
Code Size 4731 Byte
Status
Exec Time 109 ms
Memory 9728 KB

Compile Error

./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]);
      |     ^~~

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All 500 / 500 hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, random_m01.txt, random_m02.txt, random_m03.txt, random_m04.txt, random_m05.txt, random_m06.txt, random_max01.txt, random_max02.txt, random_mz01.txt, random_mz02.txt, random_mz03.txt, random_p01.txt, random_p02.txt, random_pm00.txt, random_pm01.txt, random_pm02.txt, random_pm03.txt, random_pm11.txt, random_pm12.txt, random_pmz01.txt, random_pmz02.txt, random_pmz03.txt, random_pmz04.txt, random_pmz11.txt, random_pmz12.txt, random_pmz13.txt, random_pz01.txt, random_pz02.txt, random_pz03.txt, random_z01.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
after_contest 0 / 0 after_contest_01.txt
Case Name Status Exec Time Memory
after_contest_01.txt 86 ms 9728 KB
hand_01.txt 82 ms 9652 KB
hand_02.txt 95 ms 9648 KB
hand_03.txt 91 ms 9720 KB
hand_04.txt 88 ms 9504 KB
hand_05.txt 89 ms 9460 KB
random_m01.txt 45 ms 5272 KB
random_m02.txt 19 ms 3844 KB
random_m03.txt 52 ms 5756 KB
random_m04.txt 98 ms 8780 KB
random_m05.txt 84 ms 7804 KB
random_m06.txt 22 ms 3900 KB
random_max01.txt 109 ms 9636 KB
random_max02.txt 104 ms 9620 KB
random_mz01.txt 66 ms 6516 KB
random_mz02.txt 14 ms 3928 KB
random_mz03.txt 9 ms 3900 KB
random_p01.txt 57 ms 6512 KB
random_p02.txt 50 ms 6020 KB
random_pm00.txt 32 ms 4344 KB
random_pm01.txt 41 ms 4916 KB
random_pm02.txt 74 ms 7004 KB
random_pm03.txt 45 ms 5324 KB
random_pm11.txt 60 ms 6504 KB
random_pm12.txt 19 ms 3676 KB
random_pmz01.txt 63 ms 6764 KB
random_pmz02.txt 91 ms 8784 KB
random_pmz03.txt 43 ms 5120 KB
random_pmz04.txt 48 ms 5484 KB
random_pmz11.txt 58 ms 6544 KB
random_pmz12.txt 17 ms 3824 KB
random_pmz13.txt 56 ms 6620 KB
random_pz01.txt 40 ms 5272 KB
random_pz02.txt 75 ms 8064 KB
random_pz03.txt 31 ms 7616 KB
random_z01.txt 47 ms 9044 KB
sample_01.txt 2 ms 3424 KB
sample_02.txt 3 ms 3556 KB
sample_03.txt 2 ms 3476 KB
sample_04.txt 2 ms 3424 KB