結果
問題 | No.1816 MUL-DIV Game |
ユーザー |
![]() |
提出日時 | 2022-01-21 21:36:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 17,626 bytes |
コンパイル時間 | 1,822 ms |
コンパイル使用メモリ | 206,744 KB |
最終ジャッジ日時 | 2025-01-27 13:29:55 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)#define RFOR(i, s, e) for (int i = int(e) - 1; i >= int(s); --i)#define REP(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i)#define RREP(i, n) for (int i = int(n) - 1; i >= 0; --i)#define ALL(x) (x).begin(),(x).end()#define rep(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i)#define rrep(i, n) for (int i = int(n) - 1; i >= 0; --i)#define all(x) (x).begin(),(x).end()template <class T> inline void chmin(T& a, T b) { if (b < a) { a = b; } }template <class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }template <class T> inline constexpr T square(T v) { return v * v; }template <class T, class... Params>void InstanceRun(Params&&... params) {T* m = new T;m->Run(forward<Params>(params)...);}struct Main;int main(int argc, const char* argv[]) {cin.tie(0);ios::sync_with_stdio(0);InstanceRun<Main>(argc, argv);}using ll = long long;#define int ll#define INF INT64_MAXtemplate <class T>struct arr : public vector<T> {static arr<arr<T>> D2(int y, int x, T value) {return arr<arr<T>>(y, arr<T>(x, value));}static arr<arr<arr<T>>> D3(int z, int y, int x, T value) {return arr<arr<arr<T>>>(z, arr<arr<T>>(y, arr<T>(x, value)));}static arr<T> Iota(int N, int value = 0) {auto r = arr<T>(N);r.iota(value);return r;}arr() {}arr(initializer_list<T> il) : vector<T>(il) {}explicit arr(int n) : vector<T>(n) {}arr(int n, T v) : vector<T>(n, v) {}arr(const arr& r) : vector<T>(r) {}arr(arr&& r) : vector<T>(move(r)) {}arr& operator = (const arr& r) {vector<T>::operator = (r);return *this;}arr& operator = (arr&& r) {vector<T>::operator = (move(r));return *this;}T& operator()(int i) { return (*this)[i]; }T const& operator()(int i) const { return (*this)[i]; }void init(int n, T v = T()) {this->assign(n, v);}int sz() const { return (int)this->size(); }void pb(T v) { this->push_back(v); }void sort() { std::sort(this->begin(), this->end()); }template <class F> void sort(F&& f) { std::sort(this->begin(), this->end(), f); }void rsort() { std::sort(this->begin(), this->end(), greater<T>()); }void reverse() { std::reverse(this->begin(), this->end()); }void unique_erase() { this->erase(std::unique(this->begin(), this->end()), this->end()); }bool next_permutation() { return std::next_permutation(this->begin(), this->end()); }int lower_bound(T const& v, function<bool(T, T)> p) { return std::lower_bound(this->begin(), this->end(), v, p) - this->begin(); }int lower_bound(T const& v) { return std::lower_bound(this->begin(), this->end(), v) - this->begin(); }int upper_bound(T const& v, function<bool(T, T)> p) { return std::upper_bound(this->begin(), this->end(), v, p) - this->begin(); }int upper_bound(T const& v) { return std::upper_bound(this->begin(), this->end(), v) - this->begin(); }void iota(T startValue = 0) { ::iota(this->begin(), this->end(), startValue); }void fill(T v) { ::fill(this->begin(), this->end(), v); }int find_sorted_nearest(T const& v) {int i = this->lower_bound(v);if (i >= sz()) {--i;}else if ((*this)[i] != v) {int p = i - 1;if (p >= 0) {int id = abs((*this)[i] - v);int pd = abs((*this)[p] - v);if (pd < id) {i = p;}}}return i;}int find_sorted(T const& v) {int i = this->lower_bound(v);if (i >= sz()) {return -1;}if ((*this)[i] != v) {return -1;}return i;}int find(T const& v) const {auto it = std::find(this->begin(), this->end(), v);if (it == this->end()) {return -1;}return (int)(it - this->begin());}bool is_contains(T const& v) const {auto it = std::find(this->begin(), this->end(), v);if (it == this->end()) {return false;}return true;}template <class P>void remove_if_erase(P&& predicate) { this->erase(std::remove_if(this->begin(), this->end(), predicate), this->end()); }T& emplace_back_ref() {this->emplace_back();return this->back();}friend ostream& operator<<(ostream& os, const arr<T>& p) {if (p.empty()) {return os;}os << p[0];FOR(i, 1, p.size()) {os << " " << p[i];}return os;}};using ints = arr<int>;template <class A, class B>struct pr {union {A a;A key;A first;A x;};union {B b;B value;B second;B y;};bool operator == (pr const& r) const { return a == r.a && b == r.b; }bool operator != (pr const& r) const { return !((*this) == r); }bool operator < (pr const& r) const {if (a == r.a) {return b < r.b;}return a < r.a;}pr& operator += (pr const& v) {a += v.a;b += v.b;return *this;}pr& operator -= (pr const& v) {a -= v.a;b -= v.b;return *this;}pr operator + (pr const& v) const { return pr{ a, b } += v; }pr operator - (pr const& v) const { return pr{ a, b } -= v; }pr operator - () const { return pr{ -a, -b }; }template <class C, class D>operator pr<C, D>() const {return { C(a), D(b) };}template <class T>auto operator * (T const& v) const -> pr<decltype(x * v), decltype(y * v)> {return { x * v, y * v };}template <class T>auto operator / (T const& v) const -> pr<decltype(x / v), decltype(y / v)> {return { x / v, y / v };}template <class T>pr& operator *= (T const& v) {x *= v;y *= v;return *this;}template <class T>pr& operator /= (T const& v) {x /= v;y /= v;return *this;}void flip() { swap(x, y); }friend istream& operator>>(istream& is, pr& p) {is >> p.a >> p.b;return is;}friend ostream& operator<<(ostream& os, pr const& p) {os << p.a << " " << p.b;return os;}};using pint = pr<int, int>;using pdouble = pr<double, double>;static_assert(is_pod<pint>::value, "not pod");template <class A, class B, class C>struct tr {union {A a;A first;A x;};union {B b;B second;B y;};union {C c;C third;C z;};bool operator == (tr const& r) const { return a == r.a && b == r.b && c == r.c; }bool operator != (tr const& r) const { return !((*this) == r); }bool operator < (tr const& r) const {if (a == r.a) {if (b == r.b) {return c < r.c;}return b < r.b;}return a < r.a;}tr operator + (tr v) const { return tr(x, y, z) += v; }tr operator - (tr v) const { return tr(x, y, z) -= v; }tr operator - () const { return tr{ -x, -y, -z }; }tr& operator += (tr v) {x += v.x;y += v.y;z += v.z;return *this;}tr& operator -= (tr v) {x -= v.x;y -= v.y;z -= v.z;return *this;}friend istream& operator>>(istream& is, tr& p) {is >> p.a >> p.b >> p.c;return is;}friend ostream& operator<<(ostream& os, tr const& p) {os << p.a << " " << p.b << " " << p.c;return os;}};using tint = tr<int, int, int>;static_assert(is_pod<tint>::value, "not pod");template <class T>struct arr2 {vector<vector<T>> m_vec;int m_width;int m_height;arr2() : m_width(0), m_height(0) {}arr2(int w, int h, T const& value = T()) : m_width(w), m_height(h) {m_vec.resize(h, vector<T>(w, value));}arr2(arr2 const& r) {m_vec = r.m_vec;m_width = r.m_width;m_height = r.m_height;}arr2(arr2&& r) {m_vec = move(r.m_vec);m_width = r.m_width;m_height = r.m_height;}arr2& operator=(arr2 const& r) {m_vec = r.m_vec;m_width = r.m_width;m_height = r.m_height;return *this;}arr2& operator=(arr2&& r) {m_vec = move(r.m_vec);m_width = r.m_width;m_height = r.m_height;return *this;}bool operator ==(arr2 const& r) const {return m_vec == r.m_vec;}bool operator <(arr2 const& r) const {if (m_width != r.m_width) {return m_width < r.m_width;}if (m_height != r.m_height) {return m_height < r.m_height;}REP(y, m_height) {REP(x, m_width) {if ((*this)(x, y) != r(x, y)) {return (*this)(x, y) < r(x, y);}}}return false;}pint size() const { return pint{ m_width, m_height }; }int width() const { return m_width; }int height() const { return m_height; }void clear() {m_vec.clear();m_width = 0;m_height = 0;}void init(int w, int h, T const& value = T()) {m_vec.clear();m_vec.resize(h, vector<T>(w, value));m_width = w;m_height = h;}void init(pint size, T const& value = T()) {init(size.x, size.y, value);}#if VALIDATIONvoid CheckOutOfRange(int x, int y) const {if (x < 0 || y < 0 || x >= m_width || y >= m_height) {VALIDATE_ABORT();}}void CheckOutOfRange(const pint& p) const {if (p.x < 0 || p.y < 0 || p.x >= m_width || p.y >= m_height) {VALIDATE_ABORT();}}#endifT& operator()(int x, int y) {#if VALIDATIONCheckOutOfRange(x, y);#endifreturn m_vec[y][x];}T const& operator()(int x, int y) const {#if VALIDATIONCheckOutOfRange(x, y);#endifreturn m_vec[y][x];}T& operator()(pint p) {#if VALIDATIONCheckOutOfRange(p);#endifreturn m_vec[p.y][p.x];}T const& operator()(pint p) const {#if VALIDATIONCheckOutOfRange(p);#endifreturn m_vec[p.y][p.x];}T& operator[](pint p) {#if VALIDATIONCheckOutOfRange(p);#endifreturn m_vec[p.y][p.x];}T const& operator[](pint p) const {#if VALIDATIONCheckOutOfRange(p);#endifreturn m_vec[p.y][p.x];}vector<T>& operator[](int row) {#if VALIDATIONif (row < 0 || row >= m_height) {VALIDATE_ABORT();}#endifreturn m_vec[row];}vector<T> const& operator[](int row) const {#if VALIDATIONif (row < 0 || row >= m_height) {VALIDATE_ABORT();}#endifreturn m_vec[row];}bool isIn(int x, int y) const {returnx >= 0 && x < m_width&&y >= 0 && y < m_height;}bool isIn(pint p) const { return isIn(p.x, p.y); }bool isOut(int x, int y) const {returnx < 0 || x >= m_width ||y < 0 || y >= m_height;}bool isOut(pint p) const { return isOut(p.x, p.y); }void disp(ostream& os, int w = 2) {REP(y, m_height) {REP(x, m_width) {os << setw(w) << (*this)(x, y) << " ";}os << endl;}os << endl;}};template <class K, class V>struct dic : public map<K, V> {bool get(K const& k, V* v) const {auto it = this->find(k);if (it != this->end()) {*v = it->second;return true;}return false;}typename map<K, V>::const_iterator find_less_than_equal(const K& k) const {auto it = this->lower_bound(k);if (it == this->end()) {if (it == this->begin()) {return this->end();}return prev(it);}else if (it->first == k) {return it;}else {if (it == this->begin()) {return this->end();}return prev(it);}}typename map<K, V>::const_iterator find_greater_than_equal(const K& k) const {return this->lower_bound(k);}};struct PrintStream {ostream& os_;bool printed_ = false;string space_ = " ";PrintStream(ostream& os, const string& space = " ") : os_(os), space_(space) {}template <class T>friend PrintStream& operator<<(PrintStream& ps, T&& v) {if (ps.printed_) {ps.os_ << ps.space_ << v;}else {ps.os_ << v;ps.printed_ = true;}return ps;}PrintStream& operator <<(PrintStream& (*manip)(PrintStream&)) {return (*manip)(*this);}};PrintStream& endl(PrintStream& ps) {ps.os_ << '\n';ps.printed_ = false;return ps;}struct OutputStream {ostream& os_;OutputStream(ostream& os) : os_(os) {}template <class T>friend OutputStream& operator<<(OutputStream& s, T const& v) {s.os_ << v << '\n';return s;}};#include <cstdint>using u8 = uint8_t;using u16 = uint16_t;using u32 = uint32_t;using u64 = uint64_t;using s8 = int8_t;using s16 = int16_t;using s32 = int32_t;using s64 = int64_t;using ints = arr<int>;using pint = pr<int, int>;using pints = arr<pint>;using tint = tr<int, int, int>;using tints = arr<tint>;using int2 = arr2<int>;const pints around4 = { pint{-1, 0}, pint{0, -1}, pint{1, 0}, pint{0, 1} };constexpr int gcd(int a, int b) {if (a < 0) { a = -a; }if (b < 0) { b = -b; }if (a == 0) { return b; }if (b == 0) { return a; }while (int c = a % b) {a = b;b = c;}return b;}constexpr int lcm(int a, int b) {return a / gcd(a, b) * b;}int popcount(int v) {return bitset<64>(v).count();}int64_t msb(int64_t v) {if (v == 0) return false;v |= (v >> 1);v |= (v >> 2);v |= (v >> 4);v |= (v >> 8);v |= (v >> 16);v |= (v >> 32);return popcount(v) - 1;}#ifdef LOCAL_TESTstringstream inputStream;stringstream outputStream;stringstream errorStream;istream& mis = inputStream;ostream& mos = outputStream;ostream& mes = errorStream;#elseistream& mis = cin;ostream& mos = cout;ostream& mes = cerr;#endiftemplate <class T>struct TypeInput;template <>struct TypeInput<int> {static void input(int& v, istream& is) {is >> v;}static void input(int& v, istream& is, int add) {is >> v;v += add;}};template <>struct TypeInput<double> {static void input(int& v, istream& is) {is >> v;}};template <>struct TypeInput<char> {static void input(char& v, istream& is) {is >> v;}};template <>struct TypeInput<string> {static void input(string& v, istream& is) {is >> v;}};template <class A, class B>struct TypeInput<pr<A, B>> {static void input(pr<A, B>& v, istream& is) {TypeInput<A>::input(v.a, is);TypeInput<B>::input(v.b, is);}static void input(pr<A, B>& v, istream& is, A&& addA, B&& addB) {TypeInput<A>::input(v.a, is, addA);TypeInput<B>::input(v.b, is, addB);}};template <class A, class B, class C>struct TypeInput<tr<A, B, C>> {static void input(tr<A, B, C>& v, istream& is) {TypeInput<A>::input(v.a, is);TypeInput<B>::input(v.b, is);TypeInput<C>::input(v.c, is);}static void input(tr<A, B, C>& v, istream& is, A&& addA, B&& addB, C&& addC) {TypeInput<A>::input(v.a, is, addA);TypeInput<B>::input(v.b, is, addB);TypeInput<C>::input(v.c, is, addC);}};template <class T>struct TypeInput<arr<T>> {template <class... ARGS>static void input(arr<T>& v, istream& is, int N, ARGS&&... args) {v.resize(N);REP(i, N) {TypeInput<T>::input(v[i], is, forward<ARGS>(args)...);}}};template <class T>struct TypeInput<arr2<T>> {template <class... ARGS>static void input(arr2<T>& v, istream& is, int H, int W, ARGS&&... args) {v.init(W, H);REP(y, H) {REP(x, W) {TypeInput<T>::input(v(x, y), is, forward<ARGS>(args)...);}}}};template <class... ARGS>struct InputParam {tuple<ARGS...> args_;InputParam(tuple<ARGS...>&& args) : args_(args) {}template <class T, class C = decltype(TypeInput<T>())>operator T() const {T v;apply([&](auto&&... args) { TypeInput<T>::input(v, mis, args...); }, args_);return v;}};struct inputObject {template <class T, class C = decltype(TypeInput<T>())>operator T() {T v;TypeInput<T>::input(v, mis);return v;}template <class... T>InputParam<T...> operator()(T&&... args) {return InputParam<T...>(forward_as_tuple(args...));}};struct StdIO {OutputStream out;PrintStream prn;inputObject in;StdIO() : out(mos), prn(mos) {cout << fixed << setprecision(numeric_limits<double>::digits10);cerr << fixed << setprecision(numeric_limits<double>::digits10);}};struct AlgoMain;#ifdef LOCAL_TEST#include <AlgoTest.h>#elsestruct Main{void Run(int argc, const char* argv[]){(void)argc;(void)argv;InstanceRun<AlgoMain>();}};#endifconstexpr int MOD = 998244353;template <int M>struct modint {int raw;modint() { raw = 0; }modint(int v) {if (v < 0) {raw = (v % M) + M;}else if (v >= M) {raw = v % M;}else {raw = v;}}modint operator + (modint v) const { return modint(raw) += v; }modint operator - (modint v) const { return modint(raw) -= v; }modint operator * (modint v) const { return modint(raw) *= v; }modint& operator += (modint v) {raw += v.raw;if (raw >= M) { raw -= M; }return *this;}modint& operator -= (modint v) {raw -= v.raw;if (raw < 0) { raw += M; }return *this;}modint& operator *= (modint v) {raw = (raw * v.raw) % M;return *this;}modint pow(int n) const {return modint::pow(raw, n);}static modint pow(int a, int n) {if (n < 0) {abort();}int r = 1;while (n) {if (n & 1) {r = (r * a) % M;}a = (a * a) % M;n >>= 1;}return modint(r);}modint inv() const {int a = raw;int b = M;int u = 1;int v = 0;while (b) {int t = a / b;a -= t * b;u -= t * v;swap(a, b);swap(u, v);}u %= M;if (u < 0) {u += M;}return u;}friend istream& operator>>(istream& is, modint& m) {int v;is >> v;m = modint(v);return is;}friend ostream& operator<<(ostream& os, modint const& m) {return os << m.raw;}};using mint = modint<MOD>;using mints = arr<mint>;using mint2 = arr2<mint>;struct AlgoMain : public StdIO {void Run() {int N = in;ints A = in(N);if (N == 1) {out << A[0];return;}if (A.size() % 2) {out << 1;return;}multiset<int> ms;REP(i, N) {ms.insert(A[i]);}int turn = 0;while (ms.size() > 1) {if (turn % 2 == 0) {int a = *ms.begin();ms.erase(ms.begin());int b = *ms.begin();ms.erase(ms.begin());ms.insert(a * b);}else {ms.erase(prev(ms.end()));ms.erase(prev(ms.end()));ms.insert(1);}turn++;}int ans = *ms.begin();out << ans;}};