結果
問題 | No.275 中央値を求めよ |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}