結果

問題 No.275 中央値を求めよ
コンテスト
ユーザー merom686
提出日時 2017-09-21 16:44:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,750 bytes
コンパイル時間 913 ms
コンパイル使用メモリ 77,924 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-25 00:40:32
合計ジャッジ時間 1,864 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>

template <class I, class C = std::less<>>
void insertion_sort(I first, I last, C c = C()) {
    for (I it = first; ++it < last;) {
        auto v0 = *(it - 1);
        const auto v1 = *it;
        if (c(v1, v0)) {
            I i = it;
            do {
                *i-- = v0;
            } while (i > first && c(v1, v0 = *(i - 1)));
            *i = v1;
        }
    }
}

using namespace std;
template <class I, class P>
I partition(I first, I last, P p) {
    for (I i0 = first, i1 = last;;) {
        while (i0 < i1 && p(*i0)) i0++;
        do {
            if (i0 == i1) return i0;
        } while (!p(*--i1));
        std::swap(*i0++, *i1);
    }
}

template <class I, class C = std::less<>>
void partial_quick_sort(I first, I mid0, I mid1, I last, C c = C()) {
    size_t n = last - first;
    if (n <= 64) {
        insertion_sort(first, last, c);
        return;
    }
    auto p = *(first + n / 2);
    I i0 = ::partition(first, last, [&](const auto& t) { return c(t, p); });
    if (mid0 < i0) partial_quick_sort(first, mid0, mid1, i0, c);
    I i1 = ::partition(i0, last, [&](const auto& t) { return !c(p, t); });
    if (i1 < mid1) partial_quick_sort(i1, mid0, mid1, last, c);
}

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

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int m = (n - 1) / 2;
    partial_quick_sort(a.begin(), a.begin() + m, a.begin() + (n + 2) / 2, a.end());

    if (n % 2 == 0) {
        cout << (a[m] + a[m + 1]) * 0.5 << endl;
    } else {
        cout << a[m] << endl;
    }

    return 0;
}
0