結果

問題 No.275 中央値を求めよ
ユーザー merom686merom686
提出日時 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0