結果
問題 | No.155 生放送とBGM |
ユーザー |
![]() |
提出日時 | 2021-10-20 00:49:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 14,575 bytes |
コンパイル時間 | 3,404 ms |
コンパイル使用メモリ | 260,084 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-20 06:28:51 |
合計ジャッジ時間 | 5,973 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 14 |
ソースコード
#include <bits/stdc++.h>#define REP_(i, a_, b_, a, b, ...) \for (int i = (a), END_##i = (b); i < END_##i; ++i)#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)#define ALL(x) std::begin(x), std::end(x)using Int = long long;using Real = long double;template<typename T, typename U>inline bool chmax(T &a, U b) {return a < b and ((a = std::move(b)), true);}template<typename T, typename U>inline bool chmin(T &a, U b) {return a > b and ((a = std::move(b)), true);}template<typename T>inline int ssize(const T &a) {return (int) a.size();}template<class T>inline std::ostream &print_one(const T &x, char endc) {if constexpr (std::is_same_v<T, bool>) {return std::cout << (x ? "Yes" : "No") << endc;} else {return std::cout << x << endc;}}template<class T>inline std::ostream &print(const T &x) { return print_one(x, '\n'); }template<typename T, typename... Ts>std::ostream &print(const T &head, Ts... tail) {return print_one(head, ' '), print(tail...);}inline std::ostream &print() { return std::cout << '\n'; }template<typename Container>std::ostream &print_seq(const Container &a, std::string_view sep = " ",std::string_view ends = "\n",std::ostream &os = std::cout) {auto b = std::begin(a), e = std::end(a);for (auto it = std::begin(a); it != e; ++it) {if (it != b) os << sep;os << *it;}return os << ends;}template<typename T, typename = void>struct is_iterable : std::false_type {};template<typename T>struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>())),decltype(std::end(std::declval<T>()))>>: std::true_type {};template<typename T, typename = std::enable_if_t<is_iterable<T>::value && !std::is_same<T, std::string>::value>>std::ostream &operator<<(std::ostream &os, const T &a) {return print_seq(a, ", ", "", (os << "{")) << "}";}struct CastInput {template<typename T>operator T() const {T x;std::cin >> x;return x;}struct Sized {std::size_t n;template<typename T>operator T() const {T x(n);for (auto &e: x) std::cin >> e;return x;}};Sized operator()(std::size_t n) const { return {n}; }} const in;inline void check(bool cond, const char *message = "!ERROR!") {if (not cond) throw std::runtime_error(message);}#ifdef MY_DEBUG#include "debug_dump.hpp"#else#define DUMP(...)#define cerr if(false)std::cerr#endifusing namespace std;template<typename T, int DMAX>struct NaiveMult {using value_type = T;static constexpr int dmax() { return DMAX; }static std::vector<T> multiply(const std::vector<T> &x,const std::vector<T> &y) {const int n = std::min<int>(x.size() + y.size() - 1, DMAX + 1);const int mi = std::min<int>(x.size(), n);std::vector<T> res(n);for (int i = 0; i < mi; ++i) {for (int j = 0; j < int(y.size()); ++j) {if (i + j >= n) break;res[i + j] += x[i] * y[j];}}return res;}static std::vector<T> invert(const std::vector<T> &x) {std::vector<T> res(DMAX + 1);res[0] = x[0].inv();for (int i = 1; i <= DMAX; ++i) {T s = 0;const int mj = std::min<int>(i + 1, x.size());for (int j = 1; j < mj; ++j) {s += x[j] * res[i - j];}res[i] = -res[0] * s;}return res;}};// Formal Power Series (dense format).template<typename Mult>struct DenseFPS {using T = typename Mult::value_type;static constexpr int dmax() { return Mult::dmax(); }// Coefficients of terms from x^0 to x^DMAX.std::vector<T> coeff_;DenseFPS() : coeff_(1, 0) {} // = 0 * x^0explicit DenseFPS(std::vector<T> c) : coeff_(std::move(c)) {while (size() > dmax() + 1) coeff_.pop_back();assert(size() > 0);}DenseFPS(std::initializer_list<T> init) : coeff_(init.begin(), init.end()) {while (size() > dmax() + 1) coeff_.pop_back();assert(size() > 0);}DenseFPS(const DenseFPS &other) : coeff_(other.coeff_) {}DenseFPS(DenseFPS &&other) : coeff_(std::move(other.coeff_)) {}DenseFPS &operator=(const DenseFPS &other) {coeff_ = other.coeff_;return *this;}DenseFPS &operator=(DenseFPS &&other) {coeff_ = std::move(other.coeff_);return *this;}// size <= dmax + 1inline int size() const { return static_cast<int>(coeff_.size()); }// Returns the coefficient of x^k.inline T operator[](int k) const { return (k >= size()) ? 0 : coeff_[k]; }DenseFPS &operator+=(const T &scalar) {coeff_[0] += scalar;return *this;}friend DenseFPS operator+(const DenseFPS &f, const T &scalar) {return DenseFPS(f) += scalar;}DenseFPS &operator+=(const DenseFPS &other) {if (size() < other.size()) coeff_.resize(other.size());for (int i = 0; i < other.size(); ++i) coeff_[i] += other[i];return *this;}friend DenseFPS operator+(const DenseFPS &f, const DenseFPS &g) {return DenseFPS(f) += g;}DenseFPS &operator-=(const DenseFPS &other) {if (size() < other.size()) coeff_.resize(other.size());for (int i = 0; i < other.size(); ++i) coeff_[i] -= other[i];return *this;}friend DenseFPS operator-(const DenseFPS &f, const DenseFPS &g) {return DenseFPS(f) -= g;}DenseFPS operator-() const { return *this * -1; }DenseFPS &operator*=(const T &scalar) {for (auto &x: coeff_) x *= scalar;return *this;}friend DenseFPS operator*(const DenseFPS &f, const T &scalar) {return DenseFPS(f) *= scalar;}friend DenseFPS operator*(const T &scalar, const DenseFPS &g) {return DenseFPS{scalar} *= g;}DenseFPS &operator*=(const DenseFPS &other) {return *this =DenseFPS(Mult::multiply(std::move(this->coeff_), other.coeff_));}friend DenseFPS operator*(const DenseFPS &f, const DenseFPS &g) {return DenseFPS(Mult::multiply(f.coeff_, g.coeff_));}DenseFPS &operator/=(const T &scalar) {for (auto &x: coeff_) x /= scalar;return *this;}friend DenseFPS operator/(const DenseFPS &f, const T &scalar) {return DenseFPS(f) /= scalar;}friend DenseFPS operator/(const T &scalar, const DenseFPS &g) {return DenseFPS{scalar} /= g;}DenseFPS &operator/=(const DenseFPS &other) {return *this *= DenseFPS(Mult::invert(other.coeff_));}friend DenseFPS operator/(const DenseFPS &f, const DenseFPS &g) {return f * DenseFPS(Mult::invert(g.coeff_));}DenseFPS pow(Int t) const {assert(t >= 0);DenseFPS res = {1}, base = *this;while (t) {if (t & 1) res *= base;base *= base;t >>= 1;}return res;}// Multiplies by (1 + c * x^k).void multiply2_inplace(int k, int c) {assert(k > 0);if (size() <= dmax()) {coeff_.resize(min(size() + k, dmax() + 1), 0);}for (int i = size() - 1; i >= k; --i) {coeff_[i] += coeff_[i - k] * c;}}// Multiplies by (1 + c * x^k).DenseFPS multiply2(int k, int c) const {DenseFPS res = *this;res.multiply2_inplace(k, c);return res;}// Divides by (1 + c * x^k).void divide2_inplace(int k, int c) {assert(k > 0);for (int i = k; i < size(); ++i) {coeff_[i] -= coeff_[i - k] * c;}}// Divides by (1 + c * x^k).DenseFPS divide2(int k, int c) const {DenseFPS res = *this;res.divide2_inplace(k, c);return res;}// Multiplies by x^k.void shift_inplace(int k) {if (k > 0) {if (size() <= dmax()) {coeff_.resize(min(size() + k, dmax() + 1), 0);}for (int i = size() - 1; i >= k; --i) {coeff_[i] = coeff_[i - k];}for (int i = k - 1; i >= 0; --i) {coeff_[i] = 0;}} else if (k < 0) {k *= -1;for (int i = k; i < size(); ++i) {coeff_[i - k] = coeff_[i];}for (int i = size() - k; i < size(); ++i) {// If coefficients of degrees higher than dmax() were truncated// beforehand, you lose the information. Ensure dmax() is big enough.coeff_[i] = 0;}}}// Multiplies by x^k.DenseFPS shift(int k) const {DenseFPS res = *this;res.shift_inplace(k);return res;}T eval(const T &a) const {T res = 0, x = 1;for (auto c: coeff_) {res += c * x;x *= a;}return res;}};// Formal Power Series (sparse format).template<typename T>struct SparseFPS {int size_;std::vector<int> degree_;std::vector<T> coeff_;SparseFPS() : size_(0) {}explicit SparseFPS(std::vector<std::pair<int, T>> terms): size_(terms.size()), degree_(size_), coeff_(size_) {// Sort by degree.std::sort(terms.begin(), terms.end(),[](const auto &x, const auto &y) { return x.first < y.first; });for (int i = 0; i < size_; ++i) {auto[d, c] = terms[i];assert(d >= 0);degree_[i] = d;coeff_[i] = c;}}SparseFPS(std::initializer_list<std::pair<int, T>> terms): SparseFPS(std::vector<std::pair<int, T>>(terms.begin(), terms.end())) {}inline int size() const { return size_; }inline const T &coeff(int i) const { return coeff_[i]; }inline int degree(int i) const { return degree_[i]; }int max_degree() const { return (size_ == 0) ? 0 : degree_.back(); }void emplace_back(int d, T c) {assert(d >= 0);if (not degree_.empty()) {assert(d > degree_.back());}degree_.push_back(std::move(d));coeff_.push_back(std::move(c));++size_;}// Returns the coefficient of x^d.T operator[](int d) const {auto it = std::lower_bound(degree_.begin(), degree_.end(), d);if (it == degree_.end() or *it != d) return (T) (0);int j = std::distance(degree_.begin(), it);return coeff_[j];}SparseFPS &operator+=(const T &scalar) {for (auto &x: coeff_) x += scalar;return *this;}friend SparseFPS operator+(const SparseFPS &f, const T &scalar) {SparseFPS res = f;res += scalar;return res;}SparseFPS &operator+=(const SparseFPS &other) {*this = this->add(other);return *this;}friend SparseFPS operator+(const SparseFPS &f, const SparseFPS &g) {return f.add(g);}SparseFPS &operator*=(const T &scalar) {for (auto &x: coeff_) x *= scalar;return *this;}friend SparseFPS operator*(const SparseFPS &f, const T &scalar) {SparseFPS res = f;res *= scalar;return res;}SparseFPS &operator-=(const SparseFPS &other) {*this = this->add(other * -1);return *this;}friend SparseFPS operator-(const SparseFPS &f, const SparseFPS &g) {return f.add(g * -1);}private:SparseFPS add(const SparseFPS &other) const {SparseFPS res;int j = 0; // two pointers (i, j)for (int i = 0; i < size(); ++i) {const int deg = this->degree(i);for (; j < other.size() and other.degree(j) < deg; ++j) {res.emplace_back(other.degree(j), other.coeff(j));}T c = this->coeff(i);if (j < other.size() and other.degree(j) == deg) {c += other.coeff(j);++j;}if (c != 0) {res.emplace_back(deg, c);}}for (; j < other.size(); ++j) {res.emplace_back(other.degree(j), other.coeff(j));}return res;}};// Polynomial addition (dense + sparse).template<typename FPS, typename T = typename FPS::T>FPS &operator+=(FPS &f, const SparseFPS<T> &g) {for (int i = 0; i < g.size(); ++i) {if (g.degree(i) > FPS::dmax()) break; // ignoref.coeff_[g.degree(i)] += g.coeff(i);}return f;}template<typename FPS, typename T = typename FPS::T>FPS operator+(const FPS &f, const SparseFPS<T> &g) {auto res = f;res += g;return res;}template<typename FPS, typename T = typename FPS::T>FPS operator+(const SparseFPS<T> &f, const FPS &g) {return g + f; // commutative}// Polynomial multiplication (dense * sparse).template<typename FPS, typename T = typename FPS::T>FPS &operator*=(FPS &f, const SparseFPS<T> &g) {if (g.size() == 0) {return f *= 0;}const int gd_max = g.degree(g.size() - 1);const int fd_max = f.size() - 1;const int n = std::min(fd_max + gd_max, FPS::dmax()) + 1;if (f.size() < n) f.coeff_.resize(n);T c0 = 0;int j0 = 0;if (g.degree(0) == 0) {c0 = g.coeff(0);j0 = 1;}for (int fd = n - 1; fd >= 0; --fd) {f.coeff_[fd] *= c0;for (int j = j0; j < g.size(); ++j) {int gd = g.degree(j);if (gd > fd) break;f.coeff_[fd] += f[fd - gd] * g.coeff(j);}}return f;}template<typename FPS, typename T = typename FPS::T>FPS operator*(const FPS &f, const SparseFPS<T> &g) {auto res = f;res *= g;return res;}template<typename FPS, typename T = typename FPS::T>FPS operator*(const SparseFPS<T> &f, const FPS &g) {return g * f; // commutative}// Polynomial division (dense / sparse).template<typename FPS, typename T = typename FPS::T>FPS &operator/=(FPS &f, const SparseFPS<T> &g) {assert(g.size() > 0 and g.degree(0) == 0 and g.coeff(0) != 0);const auto ic0 = T(1) / g.coeff(0);for (int fd = 0; fd < f.size(); ++fd) {for (int j = 1; j < g.size(); ++j) {int gd = g.degree(j);if (fd < gd) break;f.coeff_[fd] -= f.coeff_[fd - gd] * g.coeff(j);}f.coeff_[fd] *= ic0;}return f;}template<typename FPS, typename T = typename FPS::T>FPS operator/(const FPS &f, const SparseFPS<T> &g) {FPS res = f;res /= g;return res;}constexpr int DMAX = 300 * 60 + 5;using DF = DenseFPS<NaiveMult<Real, DMAX>>;using SF = SparseFPS<Real>;auto solve() -> Real {int n = in, L = in;L *= 60;DUMP(L);vector<int> S(n);DF f = {1.0};Int ssum = 0;REP(i, n) {int smin, ssec;scanf("%d:%d", &smin, &ssec);DUMP(i, smin, ssec);S[i] = 60 * smin + ssec;ssum += S[i];f *= SF{{0, 0.5}, {S[i], 0.5}};//DUMP(f.coeff_);}if (L >= ssum) {return n;}DUMP(S);Real ans = 0;REP(i, n) {DF g = {1.0};REP(j, n) {if (j == i) continue;g *= SF{{0, 0.5}, {S[j], 0.5}};}g.divide2_inplace(1, -1);ans += min<Real>(g[L - 1], 1);}return ans;}int main() {// ios_base::sync_with_stdio(false), cin.tie(nullptr);cout << std::fixed << std::setprecision(18);const int T = 1;//in;REP(t, T) {auto ans = solve();print(ans);}}