#315747 (C++17) No.576 E869120 and Rings

提出ソース

結果

問題	No.576 E869120 and Rings
ユーザー	Pachicobue
提出日時	2019-02-09 20:07:18
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	6,655 bytes
コンパイル時間	2,153 ms
コンパイル使用メモリ	205,288 KB
実行使用メモリ	60,284 KB
最終ジャッジ日時	2023-09-14 11:50:21
合計ジャッジ時間	47,471 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	TLE	-
testcase_02	TLE	-
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	AC	867 ms 59,968 KB
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	AC	2 ms 4,376 KB
testcase_23	AC	1 ms 4,380 KB
testcase_24	AC	1 ms 4,376 KB
testcase_25	WA	-
testcase_26	AC	1 ms 4,380 KB
testcase_27	AC	1 ms 4,380 KB
testcase_28	AC	2 ms 4,380 KB
testcase_29	AC	1 ms 4,376 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
#define show(x) std::cerr << #x << " = " << (x) << std::endl
template <typename T, std::size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template <typename T, typename A>
std::ostream& operator<<(std::ostream& os, const std::deque<T, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template <typename K, typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::multimap<K, T, C, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
    return (os << "]" << std::endl);
}
template <typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::multiset<T, C, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template <typename K, typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::map<K, T, C, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
    return (os << "]" << std::endl);
}
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) { return (os << "<" << v.first << "," << v.second << ">"); }
template <typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::set<T, C, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template <typename K, typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_multimap<K, T, H, P, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
    return (os << "]" << std::endl);
}
template <typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_multiset<T, H, P, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template <typename K, typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_map<K, T, H, P, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
    return (os << "]" << std::endl);
}
template <typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_set<T, H, P, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template <typename T, typename A>
std::ostream& operator<<(std::ostream& os, const std::vector<T, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
using ld = long double;
template <typename F>
constexpr F PI() { return 3.1415926535897932385; }
std::mt19937 mt{std::random_device{}()};
template <typename Monoid>
class SegTree
{
    static std::size_t SZ(const std::size_t n)
    {
        std::size_t ans = 1;
        for (; ans < n; ans <<= 1) {}
        return ans;
    }

public:
    using BaseMonoid = Monoid;
    using T = typename Monoid::T;
    SegTree(const std::size_t n) : size(n), half(SZ(n)), value(half << 1, Monoid::id()) {}
    template <typename InIt>
    SegTree(const InIt first, const InIt last) : size(distance(first, last)), half(SZ(size)), value(half << 1, Monoid::id())
    {
        std::copy(first, last, value.begin() + half);
        for (std::size_t i = half - 1; i >= 1; i--) { up(i); }
    }
    T get(const std::size_t a) const { return value[a + half]; }
    void set(std::size_t a, const T& val)
    {
        value[a += half] = val;
        while (a >>= 1) { up(a); }
    }
    T accumulate(std::size_t L, std::size_t R) const
    {
        T accl = Monoid::id(), accr = Monoid::id();
        for (L += half, R += half; L < R; L >>= 1, R >>= 1) {
            if (L & 1) { accl = acc(accl, value[L++]); }
            if (R & 1) { accr = acc(value[--R], accr); }
        }
        return acc(accl, accr);
    }
    template <typename Pred>
    std::size_t partitionPoint(const std::size_t L, const std::size_t R, const Pred& pred) const
    {
        auto prec = [&](auto&& self, const std::size_t index, const std::size_t left, const std::size_t right, const T& offset) -> std::pair<T, std::size_t> {
            if (right <= L or R <= left or pred(acc(offset, value[index]))) { return {Monoid::id(), R}; }
            if (index >= half) { return {value[index], index - half}; }
            const std::pair<T, std::size_t> lans = self(self, index << 1, left, (left + right) >> 1, offset);
            if (lans.second != R) { return lans; }
            return self(self, index << 1 | 1, (left + right) >> 1, right, acc(offset, lans.first));
        };
        return prec(prec, 1, 0, half, Monoid::id()).second;
    }
    std::vector<T> data() const { return std::vector<T>(value.begin() + half, value.begin() + half + size); }

private:
    void up(const std::size_t i) { value[i] = acc(value[i << 1], value[i << 1 | 1]); }
    const std::size_t size, half;
    std::vector<T> value;
    const Monoid acc{};
};
template <typename T>
std::ostream& operator<<(std::ostream& os, const SegTree<T>& seg)
{
    os << "[";
    for (const auto e : seg.data()) { os << e << ","; }
    return (os << "]\n");
}
template <typename T>
constexpr T INF() { return std::numeric_limits<T>::max() / 16; }
template <typename X>
struct Min
{
    using T = X;
    T operator()(const T& a, const T& b) const { return std::min(a, b); }
    static constexpr T id() { return INF<T>(); }
};
int main()
{
    int N, K;
    std::cin >> N >> K;
    std::vector<ld> a(N);
    std::string s;
    std::cin >> s;
    for (int i = 0; i < N; i++) { a[i] = s[i] - '0'; }
    using Seg = SegTree<Min<ld>>;
    auto ok = [&](const ld x) -> bool {
        std::vector<ld> b(2 * N);
        for (int i = 0; i < N; i++) { b[i] = -a[i] + x, b[i + N] = b[i]; }
        for (int i = 1; i < 2 * N; i++) { b[i] += b[i - 1]; }
        Seg seg(b.begin(), b.end());
        for (int i = 0; i < N; i++) {
            if (seg.accumulate(i + K, i + N) <= seg.get(i)) { return true; }
        }
        return false;
    };
    ld inf = 0, sup = 1;
    for (int i = 0; i < 30; i++) {
        const ld mid = (inf + sup) / 2;
        (ok(mid) ? inf : sup) = mid;
    }
    std::cout << std::fixed << std::setprecision(15) << inf << std::endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード