#879236 (C++17) No.2345 max(l,r)

提出ソース

結果

問題	No.2345 max(l,r)
ユーザー	LeoPro
提出日時	2023-06-09 22:15:22
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,863 bytes
コンパイル時間	2,657 ms
コンパイル使用メモリ	228,632 KB
実行使用メモリ	15,948 KB
最終ジャッジ日時	2024-06-10 13:28:38
合計ジャッジ時間	7,578 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	26 ms 6,944 KB
testcase_07	AC	26 ms 6,944 KB
testcase_08	AC	25 ms 6,940 KB
testcase_09	AC	25 ms 6,940 KB
testcase_10	AC	25 ms 6,940 KB
testcase_11	AC	26 ms 6,944 KB
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	26 ms 6,940 KB
testcase_18	AC	27 ms 6,940 KB
testcase_19	AC	27 ms 6,940 KB
testcase_20	AC	27 ms 6,940 KB
testcase_21	AC	27 ms 6,944 KB
testcase_22	AC	73 ms 12,416 KB
testcase_23	AC	74 ms 12,032 KB
testcase_24	AC	19 ms 6,940 KB
testcase_25	AC	31 ms 8,440 KB
testcase_26	AC	32 ms 6,940 KB
testcase_27	AC	31 ms 7,668 KB
testcase_28	WA	-
testcase_29	AC	18 ms 6,940 KB
testcase_30	AC	11 ms 6,940 KB
testcase_31	AC	22 ms 6,940 KB
testcase_32	AC	13 ms 6,940 KB
testcase_33	AC	13 ms 6,940 KB
testcase_34	AC	6 ms 6,940 KB
testcase_35	AC	7 ms 6,944 KB
testcase_36	AC	9 ms 6,948 KB
testcase_37	AC	11 ms 6,940 KB
testcase_38	AC	31 ms 7,936 KB
testcase_39	WA	-
testcase_40	WA	-
testcase_41	AC	31 ms 7,552 KB
testcase_42	AC	34 ms 6,940 KB
testcase_43	AC	30 ms 6,940 KB
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	RE	-
testcase_64	WA	-
testcase_65	WA	-
testcase_66	WA	-
testcase_67	WA	-
testcase_68	AC	131 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

#define int long long

using namespace std;
using ll = long long;

void solve();

template<typename ...Args>
void println(Args... args) {
    apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...));
    cout << '\n';
}

int32_t main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int t = 1;
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        solve();
    }
    return 0;
}

template<int32_t MOD>
struct ModInt {
    int value;

    ModInt() : value(0) {}

    ModInt(ll v) : value(v % MOD) { if (value < 0) value += MOD; }

#ifndef int
    ModInt(int v) : value(v < 0 ? MOD + v : v) {}
#endif

    ModInt operator+=(ModInt m) {
        value += m.value;
        if (value >= MOD) value -= MOD;
        return value;
    }

    ModInt operator-=(ModInt m) {
        value -= m.value;
        if (value < 0) value += MOD;
        return value;
    }

    ModInt operator*=(ModInt m) {
        value = (value * 1LL * m.value) % MOD;
        return value;
    }

    ModInt power(int exp) const {
        if (exp == 0) return 1;
        ModInt res = (exp & 1 ? value : 1);
        ModInt half = power(exp >> 1);
        return res * half * half;
    }

    ModInt operator/=(ModInt m) { return *this *= m.power(MOD - 2); }

    friend std::istream &operator>>(std::istream &is, ModInt &m) {
        is >> m.value;
        return is;
    }

    friend std::ostream &operator<<(std::ostream &os, const ModInt &m) {
        os << m.value;
        return os;
    }

    explicit operator int32_t() const { return value; }

    explicit operator ll() const { return value; }

    static int32_t mod() { return MOD; }
};

template<int32_t MOD>
ModInt<MOD> operator+(ModInt<MOD> a, ModInt<MOD> b) { return a += b; }

template<int32_t MOD>
ModInt<MOD> operator-(ModInt<MOD> a, ModInt<MOD> b) { return a -= b; }

template<int32_t MOD>
ModInt<MOD> operator*(ModInt<MOD> a, ModInt<MOD> b) { return a *= b; }

template<int32_t MOD>
ModInt<MOD> operator/(ModInt<MOD> a, ModInt<MOD> b) { return a /= b; }

template<int32_t MOD>
ModInt<MOD> operator==(ModInt<MOD> a, ModInt<MOD> b) { return (int32_t) a == (int32_t) b; }

template<int32_t MOD>
ModInt<MOD> operator!=(ModInt<MOD> a, ModInt<MOD> b) { return (int32_t) a != (int32_t) b; }

using mint = ModInt<998244353>;
//using mint = ModInt<(int32_t)(1e9 + 7)>;
vector<mint> f{1}, inv{1};

void precomputeFactorials(int size) {
    if (f.size() >= size) return;
    int old = f.size();
    f.resize(size, 0);
    inv.resize(size, 0);
    for (int i = old; i < size; ++i) f[i] = f[i - 1] * mint(i);
    inv[size - 1] = mint(1) / f[size - 1];
    for (int i = size - 1; i >= old; --i) inv[i - 1] = inv[i] * mint(i);
}

mint binom(int n, int k) { return f[n] * inv[k] * inv[n - k]; }

mint check(const vector<int> &row, map<int, int> cnt) {
    int s = accumulate(row.begin(), row.end(), 0LL);
    int t = 0;
    vector<int> lf(row.size()), rg(row.size());
    for (int i = 0; i < row.size(); ++i) {
        lf[i] = t;
        t += row[i];
        s -= row[i];
        rg[i] = s;
    }
    mint res = 1;
    for (int i = 0; i < row.size(); ++i) {
        int mx = max(lf[i], rg[i]);
        if (cnt[mx] < row[i]) return 0;
        res *= binom(cnt[mx], row[i]);
        cnt[mx] -= row[i];
    }
    for (auto [k, v] : cnt) {
        if (v != 0) return 0;
    }
    return res;
}

void solve() {
    int n, m;
    cin >> n >> m;
    precomputeFactorials(m + 100);
    vector<int> a(n);
    for (int &x: a) cin >> x;
    map<int, int> t;
    for (int x: a) t[x]++;
    vector<pair<int, int>> cnt(t.begin(), t.end());
    reverse(cnt.begin(), cnt.end());
    mint ans = 1;
    vector<int> lfcur, rgcur;
    vector<int> lf, rg;
    int lfs = 0, rgs = 0;
    for (auto &[mx, cn]: cnt) {
        int mn = n - mx;
        if (cn + lfs == mn) {
            lfcur.push_back(cn);
            lfs += cn;
        } else if (cn + rgs == mn) {
            rgcur.push_back(cn);
            rgs += cn;
        } else if (cn + lfs + rgs == mn + mn) {
            lfcur.push_back(mn - lfs);
            lfs += mn - lfs;
            rgcur.push_back(mn - rgs);
            rgs += mn - rgs;
        } else {
            return println(0);
        }
        if (lfs == rgs) {
            if (lf != rg) ans *= 2;
            for (int x: lfcur) lf.push_back(x);
            lf.clear();
            for (int x: rgcur) rg.push_back(x);
            rg.clear();
        }
    }
    auto concat = lfcur;
    for (int j = (int) rgcur.size() - 1; j >= 0; --j) concat.push_back(rgcur[j]);
    auto rconcat = concat;
    reverse(rconcat.begin(), rconcat.end());
    if (concat != rconcat) ans *= 2;
    for (int x: concat) lf.push_back(x);
    reverse(rg.begin(), rg.end());
    for (int x: rg) lf.push_back(x);
    mint o = check(lf, t);
    cout << ans * binom(m, lf.size()) * o << '\n';
}

yukicoder

結果

テストケース

ソースコード