Submission #40692102

Source Code Expand

#line 1 "d.cpp"

#include <bits/stdc++.h>
#line 4 "library/src/math/gcd.hpp"
namespace kyopro {
template <typename T> constexpr T _gcd(T a, T b) {
    assert(a >= 0 && b >= 0);
    if (a == 0 || b == 0) return a + b;
    int d = std::min<T>(__builtin_ctzll(a), __builtin_ctzll(b));
    a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b);
    while (a != b) {
        if (a == 0 || b == 0) {
            return a + b;
        }
        if (a > b) {
            a -= b;
            a >>= __builtin_ctzll(a);
        } else {
            b -= a;
            b >>= __builtin_ctzll(b);
        }
    }

    return a << d;
}
template <typename T> constexpr T ext_gcd(T a, T b, T& x, T& y) {
    x = 1, y = 0;
    T nx = 0, ny = 1;
    while (b) {
        T q = a / b;
        std::tie(a, b) = std::pair<T, T>{b, a % b};
        std::tie(x, nx) = std::pair<T, T>{nx, x - nx * q};
        std::tie(y, ny) = std::pair<T, T>{ny, y - ny * q};
    }
    return a;
}
};  // namespace kyopro
#line 5 "library/src/math/static_modint.hpp"
namespace kyopro {
template <__uint64_t mod> class static_modint {
  private:
    using mint = static_modint<mod>;
    using i64 = long long;
    using u64 = unsigned long long;
    using u128 = __uint128_t;
    using i128 = __int128_t;

    u64 v;
    constexpr inline u64 normalize(i64 v_) const {
        v_ %= mod;
        if (v_ < 0) {
            v_ += mod;
        }
        return v_;
    }

  public:
    constexpr static_modint() : v(0) {}
    constexpr static_modint(const i64& v_) : v(normalize(v_)) {}

    // operator
    constexpr u64 val() const { return v; }
    constexpr mint& operator+=(const mint& rhs) {
        v += rhs.val();
        if (v >= mod) {
            v -= mod;
        }
        return (*this);
    }
    constexpr mint& operator-=(const mint& rhs) {
        v += mod - rhs.val();
        if (v >= mod) {
            v -= mod;
        }
        return (*this);
    }
    constexpr mint& operator*=(const mint& rhs) {
        v = (u128)v * rhs.val() % mod;
        return (*this);
    }

    constexpr mint operator+(const mint& r) const { return mint(*this) += r; }
    constexpr mint operator-(const mint& r) const { return mint(*this) -= r; }
    constexpr mint operator*(const mint& r) const { return mint(*this) *= r; }

    constexpr mint& operator+=(const i64& rhs) {
        (*this) += mint(rhs);
        return (*this);
    }
    constexpr mint& operator-=(const i64& rhs) {
        (*this) -= mint(rhs);
        return (*this);
    }
    constexpr mint& operator*=(const i64& rhs) {
        (*this) *= mint(rhs);
        return (*this);
    }
    constexpr friend mint operator+(const i64& l, const mint& r) {
        return mint(l) += r;
    }
    constexpr friend mint operator-(const i64& l, const mint& r) {
        return mint(l) -= r;
    }
    constexpr friend mint operator*(const i64& l, const mint& r) {
        return mint(l) *= r;
    }

    constexpr mint operator+(const i64& r) { return mint(*this) += r; }
    constexpr mint operator-(const i64& r) { return mint(*this) -= r; }
    constexpr mint operator*(const i64& r) { return mint(*this) *= r; }

    constexpr mint& operator=(const i64& r) { return (*this) = mint(r); }

    constexpr bool operator==(const mint& r) const {
        return (*this).val() == r.val();
    }

    template <typename T> constexpr mint pow(T e) const {
        mint ans(1), base(*this);
        while (e) {
            if (e & 1) {
                ans *= base;
            }
            base *= base;
            e >>= 1;
        }
        return ans;
    }
    constexpr inline mint inv() const {
        long long x, y;
        auto d = ext_gcd((long long)mod, (long long)v, x, y);
        assert(d == 1);
        return mint(y);
    }

    constexpr mint& operator/=(const mint& r) { return (*this) *= r.inv(); }
    constexpr mint inv(const mint& r) const { return mint(*this) *= r.inv(); }
    constexpr friend mint operator/(const mint& l, const i64& r) {
        return mint(l) /= mint(r);
    }
    constexpr friend mint operator/(const i64& l, const mint& r) {
        return mint(l) /= mint(r);
    }

    // iostream
    constexpr friend std::ostream& operator<<(std::ostream& os,
                                              const mint& mt) {
        os << mt.val();
        return os;
    }
    constexpr friend std::istream& operator>>(std::istream& is, mint& mt) {
        i64 v_;
        is >> v_;
        mt = v_;
        return is;
    }
};
template <__uint32_t mod> class static_modint32 {
  private:
    using mint = static_modint32<mod>;
    using i32 = __int32_t;
    using u32 = __uint32_t;
    using i64 = __int64_t;
    using u64 = __uint64_t;

    u32 v;
    constexpr inline u32 normalize(i64 v_) const {
        v_ %= mod;
        if (v_ < 0) {
            v_ += mod;
        }
        return v_;
    }

  public:
    constexpr static_modint32() : v(0) {}
    constexpr static_modint32(const i64& v_) : v(normalize(v_)) {}

    // operator
    constexpr u64 val() const { return (u64)v; }
    constexpr mint& operator+=(const mint& rhs) {
        v += rhs.val();
        if (v >= mod) {
            v -= mod;
        }
        return (*this);
    }
    constexpr mint& operator-=(const mint& rhs) {
        v += mod - rhs.val();
        if (v >= mod) {
            v -= mod;
        }
        return (*this);
    }
    constexpr mint& operator*=(const mint& rhs) {
        v = (u64)v * rhs.val() % mod;
        return (*this);
    }

    constexpr mint operator+(const mint& r) const { return mint(*this) += r; }
    constexpr mint operator-(const mint& r) const { return mint(*this) -= r; }
    constexpr mint operator*(const mint& r) const { return mint(*this) *= r; }

    constexpr mint& operator+=(const i64& rhs) {
        (*this) += mint(rhs);
        return (*this);
    }
    constexpr mint& operator-=(const i64& rhs) {
        (*this) -= mint(rhs);
        return (*this);
    }
    constexpr mint& operator*=(const i64& rhs) {
        (*this) *= mint(rhs);
        return (*this);
    }
    constexpr friend mint operator+(const i64& l, const mint& r) {
        return mint(l) += r;
    }
    constexpr friend mint operator-(const i64& l, const mint& r) {
        return mint(l) -= r;
    }
    constexpr friend mint operator*(const i64& l, const mint& r) {
        return mint(l) *= r;
    }

    constexpr mint operator+(const i64& r) { return mint(*this) += r; }
    constexpr mint operator-(const i64& r) { return mint(*this) -= r; }
    constexpr mint operator*(const i64& r) { return mint(*this) *= r; }

    constexpr mint& operator=(const i64& r) { return (*this) = mint(r); }

    constexpr bool operator==(const mint& r) const {
        return (*this).val() == r.val();
    }
    template <typename T> constexpr mint pow(T e) const {
        mint ans(1), base(*this);
        while (e) {
            if (e & 1) {
                ans *= base;
            }
            base *= base;
            e >>= 1;
        }
        return ans;
    }

    constexpr inline mint inv() const {
        long long x, y;
        auto d = ext_gcd((long long)mod, (long long)v, x, y);
        assert(d == 1);
        return mint(y);
    }

    constexpr mint& operator/=(const mint& r) { return (*this) *= r.inv(); }
    constexpr mint operator/(const mint& r) const {
        return mint(*this) *= r.inv();
    }
    constexpr friend mint operator/(const mint& l, const i64& r) {
        return mint(l) /= mint(r);
    }
    constexpr friend mint operator/(const i64& l, const mint& r) {
        return mint(l) /= mint(r);
    }

    // iostream
    constexpr friend std::ostream& operator<<(std::ostream& os,
                                              const mint& mt) {
        os << mt.val();
        return os;
    }
    constexpr friend std::istream& operator>>(std::istream& is, mint& mt) {
        i64 v_;
        is >> v_;
        mt = v_;
        return is;
    }
};
};  // namespace kyopro

/// @brief static modint(静的modint)
/// @docs docs/math/static_modint.md
#line 4 "d.cpp"
using namespace std;
using mint = kyopro::static_modint32<998244353>;
int main() {
    mint cur = 1;
    mint pw = 1;
    queue<int> que;
    const mint inv10 = mint(10).inv();
    que.emplace(1);
    int q;
    scanf("%d", &q);
    while (q--) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int x;
            scanf("%d", &x);
            cur *= 10;
            cur += x;
            que.emplace(x);
            pw *= 10;
        } else if (t == 2) {
            cur -= pw * que.front();
            pw *= inv10;
            que.pop();
        } else {
            printf("%lld\n", cur.val());
        }
    }
}

Submission Info

Submission Time
Task D - Writing a Numeral
User AC2K
Language C++ (GCC 9.2.1)
Score 400
Code Size 8996 Byte
Status AC
Exec Time 86 ms
Memory 6184 KiB

Compile Error

d.cpp: In function ‘int main()’:
d.cpp:29:20: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘kyopro::static_modint32<998244353>::u64’ {aka ‘long unsigned int’} [-Wformat=]
d.cpp:13:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
d.cpp:16:14: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
d.cpp:19:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 20
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 02_add_00.txt, 02_add_01.txt, 02_add_02.txt, 02_add_03.txt, 03_del_00.txt, 03_del_01.txt, 03_del_02.txt, 03_del_03.txt, 03_del_04.txt, 03_del_05.txt, 04_one_00.txt, 04_one_01.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 9 ms 3616 KiB
00_sample_01.txt AC 2 ms 3708 KiB
00_sample_02.txt AC 2 ms 3616 KiB
01_rnd_00.txt AC 81 ms 3624 KiB
01_rnd_01.txt AC 79 ms 3616 KiB
01_rnd_02.txt AC 76 ms 3716 KiB
01_rnd_03.txt AC 76 ms 3708 KiB
01_rnd_04.txt AC 75 ms 3628 KiB
02_add_00.txt AC 86 ms 4608 KiB
02_add_01.txt AC 85 ms 4616 KiB
02_add_02.txt AC 80 ms 6184 KiB
02_add_03.txt AC 78 ms 6180 KiB
03_del_00.txt AC 72 ms 4512 KiB
03_del_01.txt AC 71 ms 4516 KiB
03_del_02.txt AC 61 ms 4484 KiB
03_del_03.txt AC 63 ms 4416 KiB
03_del_04.txt AC 62 ms 4484 KiB
03_del_05.txt AC 65 ms 4564 KiB
04_one_00.txt AC 2 ms 3776 KiB
04_one_01.txt AC 86 ms 3692 KiB