結果
| 問題 | No.155 生放送とBGM |
| ユーザー |
 keijak
|
| 提出日時 | 2021-10-20 00:49:28 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,575 bytes |
| コンパイル時間 | 3,393 ms |
| コンパイル使用メモリ | 260,412 KB |
| 実行使用メモリ | 4,780 KB |
| 最終ジャッジ日時 | 2023-10-20 10:54:24 |
| 合計ジャッジ時間 | 6,341 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | AC | 6 ms
4,348 KB |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
ソースコード
#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
#endif
using 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^0
explicit 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 + 1
inline 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; // ignore
f.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);
}
}