verify/yukicoder-275.test.cpp

• View this file on GitHub
• Last update: 2026-05-29 20:48:10+09:00
• Problem: https://yukicoder.me/problems/no/275

Depends on

• 値の追加・削除と中央値取得 (structure/others/dynamic-median.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/275
// competitive-verifier: ERROR 0

#include <iomanip>
#include <iostream>

#include "../structure/others/dynamic-median.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    DynamicMedian<long long> median;
    for (int i = 0; i < n; ++i) {
        long long a;
        std::cin >> a;
        median.add(a);
    }

    const long double answer =
        median.median<long double>(DynamicMedianMode::Average);
    std::cout << std::fixed << std::setprecision(1) << answer << '\n';
    return 0;
}

#line 1 "verify/yukicoder-275.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/275
// competitive-verifier: ERROR 0

#include <iomanip>
#include <iostream>

#line 1 "structure/others/dynamic-median.hpp"



// 値の多重集合に対して追加、削除、中央値取得を行う。
// 中央値は下側、上側、両側の算術平均から選べる。
// T はコピー可能で、std::multiset で扱える比較を持つ型を仮定する。
// median は空でないことを仮定する。
// add, erase は O(log N)、median は O(1) である。

#include <cassert>
#include <set>
#include <type_traits>

enum class DynamicMedianMode { Lower, Upper, Average };

template <class T> struct DynamicMedian {
    std::multiset<T> lower_values;
    std::multiset<T> upper_values;

    void add(T x) {
        if (lower_values.empty() || !(*lower_values.rbegin() < x)) {
            lower_values.insert(x);
        } else {
            upper_values.insert(x);
        }
        balance();
    }

    bool erase(T x) {
        auto lower_itr = lower_values.find(x);
        if (lower_itr != lower_values.end()) {
            lower_values.erase(lower_itr);
            balance();
            return true;
        }

        auto upper_itr = upper_values.find(x);
        if (upper_itr != upper_values.end()) {
            upper_values.erase(upper_itr);
            balance();
            return true;
        }

        return false;
    }

    template <class Result = T>
    Result median(DynamicMedianMode mode = DynamicMedianMode::Lower) const {
        assert(!lower_values.empty());
        const T &lower_median = *lower_values.rbegin();

        if (mode == DynamicMedianMode::Lower) {
            return static_cast<Result>(lower_median);
        }
        if (lower_values.size() != upper_values.size()) {
            return static_cast<Result>(lower_median);
        }

        const T &upper_median = *upper_values.begin();
        if (mode == DynamicMedianMode::Upper) {
            return static_cast<Result>(upper_median);
        }

        assert(mode == DynamicMedianMode::Average);
        const Result lower = static_cast<Result>(lower_median);
        const Result upper = static_cast<Result>(upper_median);
        if constexpr (std::is_integral_v<Result>) {
            if constexpr (std::is_signed_v<Result>) {
                if (lower < 0 && 0 < upper) {
                    return (lower + upper) / 2;
                }
            }
            return lower / 2 + upper / 2 + (lower % 2 + upper % 2) / 2;
        } else if constexpr (requires(Result lhs, Result rhs) {
                                 (lhs + rhs) / Result(2);
                             }) {
            return (lower + upper) / Result(2);
        } else {
            assert(false);
            return static_cast<Result>(lower_median);
        }
    }

  private:
    void balance() {
        while (lower_values.size() < upper_values.size()) {
            lower_values.insert(*upper_values.begin());
            upper_values.erase(upper_values.begin());
        }
        while (lower_values.size() > upper_values.size() + 1) {
            auto itr = lower_values.end();
            --itr;
            upper_values.insert(*itr);
            lower_values.erase(itr);
        }
    }
};


#line 8 "verify/yukicoder-275.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    DynamicMedian<long long> median;
    for (int i = 0; i < n; ++i) {
        long long a;
        std::cin >> a;
        median.add(a);
    }

    const long double answer =
        median.median<long double>(DynamicMedianMode::Average);
    std::cout << std::fixed << std::setprecision(1) << answer << '\n';
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	99_system_test1	AC	3 ms	4 MB
g++	99_system_test2	AC	2 ms	4 MB
g++	99_system_test3	AC	2 ms	4 MB
g++	sample1	AC	2 ms	4 MB
g++	sample2	AC	2 ms	4 MB
g++	sample3	AC	2 ms	4 MB
g++	system_test1	AC	2 ms	4 MB
g++	system_test2	AC	3 ms	4 MB
g++	system_test3	AC	2 ms	4 MB
g++	system_test4	AC	2 ms	4 MB
g++	system_test5	AC	2 ms	4 MB
g++	test1	AC	2 ms	4 MB
g++	test10	AC	3 ms	4 MB
g++	test11	AC	2 ms	4 MB
g++	test12	AC	3 ms	4 MB
g++	test13	AC	2 ms	4 MB
g++	test14	AC	2 ms	4 MB
g++	test15	AC	3 ms	4 MB
g++	test16	AC	3 ms	4 MB
g++	test17	AC	3 ms	4 MB
g++	test18	AC	2 ms	4 MB
g++	test19	AC	2 ms	4 MB
g++	test2	AC	2 ms	4 MB
g++	test20	AC	2 ms	4 MB
g++	test21	AC	3 ms	4 MB
g++	test22	AC	2 ms	4 MB
g++	test23	AC	3 ms	4 MB
g++	test24	AC	2 ms	4 MB
g++	test25	AC	3 ms	4 MB
g++	test26	AC	2 ms	4 MB
g++	test27	AC	2 ms	4 MB
g++	test28	AC	2 ms	4 MB
g++	test29	AC	2 ms	4 MB
g++	test3	AC	2 ms	4 MB
g++	test30	AC	3 ms	4 MB
g++	test4	AC	2 ms	4 MB
g++	test5	AC	3 ms	4 MB
g++	test6	AC	3 ms	4 MB
g++	test7	AC	3 ms	4 MB
g++	test8	AC	2 ms	4 MB
g++	test9	AC	3 ms	4 MB
clang++	99_system_test1	AC	3 ms	4 MB
clang++	99_system_test2	AC	2 ms	4 MB
clang++	99_system_test3	AC	2 ms	4 MB
clang++	sample1	AC	2 ms	4 MB
clang++	sample2	AC	2 ms	4 MB
clang++	sample3	AC	2 ms	4 MB
clang++	system_test1	AC	2 ms	4 MB
clang++	system_test2	AC	2 ms	4 MB
clang++	system_test3	AC	2 ms	4 MB
clang++	system_test4	AC	2 ms	4 MB
clang++	system_test5	AC	2 ms	4 MB
clang++	test1	AC	2 ms	4 MB
clang++	test10	AC	3 ms	4 MB
clang++	test11	AC	2 ms	4 MB
clang++	test12	AC	3 ms	4 MB
clang++	test13	AC	2 ms	4 MB
clang++	test14	AC	2 ms	4 MB
clang++	test15	AC	3 ms	4 MB
clang++	test16	AC	3 ms	4 MB
clang++	test17	AC	3 ms	4 MB
clang++	test18	AC	2 ms	4 MB
clang++	test19	AC	2 ms	4 MB
clang++	test2	AC	2 ms	4 MB
clang++	test20	AC	2 ms	4 MB
clang++	test21	AC	3 ms	4 MB
clang++	test22	AC	2 ms	4 MB
clang++	test23	AC	3 ms	4 MB
clang++	test24	AC	2 ms	4 MB
clang++	test25	AC	3 ms	4 MB
clang++	test26	AC	2 ms	4 MB
clang++	test27	AC	2 ms	4 MB
clang++	test28	AC	2 ms	4 MB
clang++	test29	AC	2 ms	4 MB
clang++	test3	AC	2 ms	4 MB
clang++	test30	AC	3 ms	4 MB
clang++	test4	AC	2 ms	4 MB
clang++	test5	AC	3 ms	4 MB
clang++	test6	AC	3 ms	4 MB
clang++	test7	AC	3 ms	4 MB
clang++	test8	AC	2 ms	4 MB
clang++	test9	AC	3 ms	4 MB

Back to top page