結果

問題 No.1608 Yet Another Ants Problem
ユーザー hitonanodehitonanode
提出日時 2021-07-16 23:26:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,137 bytes
コンパイル時間 1,144 ms
コンパイル使用メモリ 91,708 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 11:02:31
合計ジャッジ時間 1,942 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 3 ms
6,940 KB
testcase_15 AC 4 ms
6,940 KB
testcase_16 AC 4 ms
6,940 KB
testcase_17 AC 4 ms
6,940 KB
testcase_18 AC 4 ms
6,940 KB
testcase_19 AC 1 ms
6,944 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 3 ms
6,944 KB
testcase_22 AC 3 ms
6,940 KB
testcase_23 AC 3 ms
6,940 KB
testcase_24 AC 4 ms
6,944 KB
testcase_25 AC 3 ms
6,944 KB
testcase_26 AC 3 ms
6,944 KB
testcase_27 AC 4 ms
6,944 KB
testcase_28 AC 4 ms
6,940 KB
testcase_29 AC 3 ms
6,944 KB
testcase_30 AC 4 ms
6,944 KB
testcase_31 AC 4 ms
6,940 KB
testcase_32 AC 4 ms
6,940 KB
testcase_33 AC 3 ms
6,940 KB
testcase_34 AC 3 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }

template <int md> struct ModInt {
#if __cplusplus >= 201402L
#define MDCONST constexpr
#else
#define MDCONST
#endif
    int val;
    MDCONST ModInt() : val(0) {}
    MDCONST ModInt &_setval(int v) { return val = (v >= md ? v - md : v), *this; }
    MDCONST ModInt(int v) { _setval(v); }
    MDCONST explicit operator bool() const { return val != 0; }
    MDCONST ModInt operator+(const ModInt &x) const { return ModInt()._setval(val + x.val); }
    MDCONST ModInt operator-(const ModInt &x) const { return ModInt()._setval(val - x.val + md); }
    MDCONST ModInt operator-() const { return ModInt()._setval(md - val); }
    MDCONST ModInt &operator+=(const ModInt &x) { return *this = *this + x; }
    MDCONST ModInt &operator-=(const ModInt &x) { return *this = *this - x; }
    MDCONST friend std::ostream &operator<<(std::ostream &os, const ModInt &x) { return os << x.val; }
};
using mint = ModInt<998244353>;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, L;
    cin >> N >> L;
    vector<int> A(N);
    for (auto &x : A) cin >> x;

    vector<vector<int>> w2i(N);
    REP(i, N) {
        if (i and A[i - 1] >= L - A[i]) break;
        int r = lower_bound(A.begin() + i + 1, A.end(), L - A[i]) - A.begin();
        w2i[N - 1 - (r - i - 1)].push_back(i + (r - i - 1));
    }
    REP(i, N) {
        if (i + 1 < N and L - A[i + 1] > A[i]) continue;
        int l = lower_bound(A.begin(), A.begin() + i, L - A[i]) - A.begin() - 1;
        w2i[N - 1 - (i - l - 1)].push_back(l + 1 + (i - l - 1));
    }
    vector<mint> ret(N);
    for (auto is : w2i) {
        REP(i, ret.size() - 1) ret[i] += ret[i + 1];
        for (auto i : is) ret[i] += 1;
    }
    for (auto x : ret) cout << x << '\n';
}
0