結果

問題 No.1816 MUL-DIV Game
ユーザー bowwowforeach
提出日時 2022-01-21 21:31:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 17,622 bytes
コンパイル時間 2,858 ms
コンパイル使用メモリ 207,484 KB
最終ジャッジ日時 2025-01-27 13:27:23
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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_MAX
template <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 VALIDATION
void 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();
}
}
#endif
T& operator()(int x, int y) {
#if VALIDATION
CheckOutOfRange(x, y);
#endif
return m_vec[y][x];
}
T const& operator()(int x, int y) const {
#if VALIDATION
CheckOutOfRange(x, y);
#endif
return m_vec[y][x];
}
T& operator()(pint p) {
#if VALIDATION
CheckOutOfRange(p);
#endif
return m_vec[p.y][p.x];
}
T const& operator()(pint p) const {
#if VALIDATION
CheckOutOfRange(p);
#endif
return m_vec[p.y][p.x];
}
T& operator[](pint p) {
#if VALIDATION
CheckOutOfRange(p);
#endif
return m_vec[p.y][p.x];
}
T const& operator[](pint p) const {
#if VALIDATION
CheckOutOfRange(p);
#endif
return m_vec[p.y][p.x];
}
vector<T>& operator[](int row) {
#if VALIDATION
if (row < 0 || row >= m_height) {
VALIDATE_ABORT();
}
#endif
return m_vec[row];
}
vector<T> const& operator[](int row) const {
#if VALIDATION
if (row < 0 || row >= m_height) {
VALIDATE_ABORT();
}
#endif
return m_vec[row];
}
bool isIn(int x, int y) const {
return
x >= 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 {
return
x < 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_TEST
stringstream inputStream;
stringstream outputStream;
stringstream errorStream;
istream& mis = inputStream;
ostream& mos = outputStream;
ostream& mes = errorStream;
#else
istream& mis = cin;
ostream& mos = cout;
ostream& mes = cerr;
#endif
template <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>
#else
struct Main
{
void Run(int argc, const char* argv[])
{
(void)argc;
(void)argv;
InstanceRun<AlgoMain>();
}
};
#endif
constexpr 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 == 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;
}
};
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0