結果
問題 | No.275 中央値を求めよ |
ユーザー |
![]() |
提出日時 | 2015-09-05 00:57:48 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 1,000 ms |
コード長 | 2,819 bytes |
コンパイル時間 | 910 ms |
コンパイル使用メモリ | 61,656 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-24 23:11:06 |
合計ジャッジ時間 | 1,810 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <iostream>#include <algorithm>#include <sstream>using namespace std;// http://www.prefield.com/algorithm/container/avl_tree.htmltemplate <class T>struct avl_tree {struct node {T key;int size, height;node *child[2];node(const T &key) : key(key), size(1), height(1) {child[0] = child[1] = 0; }} *root;typedef node *pointer;avl_tree() { root = NULL; }pointer find(const T &key) { return find(root, key); }node *find(node *t, const T &key) {if (t == NULL) return NULL;if (key == t->key) return t;else if (key < t->key) return find(t->child[0], key);else return find(t->child[1], key);}void insert(const T &key) { root = insert(root, new node(key)); }node *insert(node *t, node *x) {if (t == NULL) return x;if (x->key <= t->key) t->child[0] = insert(t->child[0], x);else t->child[1] = insert(t->child[1], x);t->size += 1;return balance(t);}void erase(const T &key) { root = erase(root, key); }node *erase(node *t, const T &x) {if (t == NULL) return NULL;if (x == t->key) {return move_down(t->child[0], t->child[1]);} else {if (x < t->key) t->child[0] = erase(t->child[0], x);else t->child[1] = erase(t->child[1], x);t->size -= 1;return balance(t);}}node *move_down(node *t, node *rhs) {if (t == NULL) return rhs;t->child[1] = move_down(t->child[1], rhs);return balance(t);}#define sz(t) (t ? t->size : 0)#define ht(t) (t ? t->height : 0)node *rotate(node *t, int l, int r) {node *s = t->child[r];t->child[r] = s->child[l];s->child[l] = balance(t);if (t) t->size = sz(t->child[0]) + sz(t->child[1]) + 1;if (s) s->size = sz(s->child[0]) + sz(s->child[1]) + 1;return balance(s);}node *balance(node *t) {for (int i = 0; i < 2; ++i) {if (ht(t->child[!i]) - ht(t->child[i]) < -1) {if (ht(t->child[i]->child[!i]) - ht(t->child[i]->child[i]) > 0)t->child[i] = rotate(t->child[i], i, !i);return rotate(t, !i, i);}}if (t) t->height = max(ht(t->child[0]), ht(t->child[1])) + 1;if (t) t->size = sz(t->child[0]) + sz(t->child[1]) + 1;return t;}pointer rank(int k) const { return rank(root, k); }pointer rank(node *t, int k) const {if (t) {int m = sz(t->child[0]);if (k == m) return t;if (k < m) return rank(t->child[0], k);return rank(t->child[1], k - m - 1);}return NULL;}};int main(int argc, char *argv[]){int N;cin >> N;avl_tree<int> t;for (int i = 0; i < N; ++i) {int a;cin >> a;t.insert(a);}double ans = (t.rank((N-1) / 2)->key + t.rank(N / 2)->key) * 0.5;cout << ans << endl;return 0;}