結果

問題 No.182 新規性の虜
コンテスト
ユーザー yudedako
提出日時 2016-03-15 20:32:19
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 83 ms / 5,000 ms
コード長 5,556 bytes
コンパイル時間 1,596 ms
コンパイル使用メモリ 76,228 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-12-27 02:12:39
合計ジャッジ時間 2,853 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘bool AVLTree::increase_right()’:
main.cpp:171:1: warning: control reaches end of non-void function [-Wreturn-type]
  171 | }
      | ^
main.cpp: In member function ‘bool AVLTree::increase_left()’:
main.cpp:185:1: warning: control reaches end of non-void function [-Wreturn-type]
  185 | }
      | ^

ソースコード

diff # 

#include <memory>
#include <iostream>
#include <functional>
class AVLTree {
	enum class Bias : char {
		Left, Right, Equal
	};
	using Key = int;
	using Value = int;
public:
	AVLTree(const Key &, const Value & = Value{}, const std::shared_ptr<AVLTree> & = { nullptr }, const std::shared_ptr<AVLTree> & = { nullptr }, const Bias & = Bias::Equal);
	AVLTree();
	void incriment(const Key &);
	Value sum() const;
	AVLTree &map(const std::function<Value(const Value &)> &);
	int depth() const;
	void show() const;
private:
	std::shared_ptr<AVLTree> left, right;
	Key key;
	Value val;
	Bias bias;
	void show_all() const;
	bool sub_insert(const Key &, const Value &);
	void turn_right();
	void turn_left();
	void double_right();
	void double_left();
	bool increase_right();
	bool increase_left();
	void sub_map(const std::function<Value(const Value &)> &);
};
AVLTree::AVLTree(const Key &k, const Value &v, const std::shared_ptr<AVLTree> &l, const std::shared_ptr<AVLTree> &r, const Bias &b) :key{ k }, val{ v }, left{ l }, right{ r }, bias{ b } {};
AVLTree::AVLTree() :key{}, val{}, left{ nullptr }, right{ nullptr }, bias{ Bias::Equal } {};
void AVLTree::incriment(const Key &k) {
	sub_insert(k, 1);
}
AVLTree::Value AVLTree::sum() const {
	Value res = val;
	if (left) res += left->sum();
	if (right) res += right->sum();
	return res;
}
AVLTree &AVLTree::map(const std::function<Value(const Value &)> &f) {
	sub_map(f);
	return *this;
}
int AVLTree::depth() const {
	int res = 1;
	if (left) res += left->depth();
	if (right && right->depth() >= res) res = right->depth() + 1;
	return res;
}
void AVLTree::show() const {
	show_all();
	std::cout << std::endl;
}
void AVLTree::show_all() const {
	std::cout << "-(" << key << "," << val << ")";
	if (left) {	left->show_all(); }
	if (right) { right->show_all(); }
}
bool AVLTree::sub_insert(const Key &k, const Value &v) {
	if (k == key) {
		val += v; return false;
	}
	else if (k < key) {
		if (!left || left->sub_insert(k, v)) {
			if (!left) left = std::make_shared<AVLTree>(AVLTree(k, v));
			return increase_left();
		}
		else return false;
	}
	else {
		if (!right || right->sub_insert(k, v)) {
			if (!right) right = std::make_shared<AVLTree>(AVLTree(k, v));
			return increase_right();
		}
		else return false;
	}
}
void AVLTree::turn_right() {
	const auto a = left->left;
	const auto b = left->right;
	const auto c = right;
	switch (left->bias) {
	case Bias::Equal:
		right = std::make_shared<AVLTree>(AVLTree(key, val, b, c, Bias::Left));
		bias = Bias::Right;
		break;
	case Bias::Left:
		right = std::make_shared<AVLTree>(AVLTree(key, val, b, c, Bias::Equal));
		bias = Bias::Equal;
	}
	key = left->key; val = left->val;
	left = a;
}
void AVLTree::turn_left() {
	const auto a = left;
	const auto b = right->left;
	const auto c = right->right;
	switch (right->bias) {
	case Bias::Equal:
		left = std::make_shared<AVLTree>(AVLTree(key, val, a, b, Bias::Right));
		bias = Bias::Left;
		break;
	case Bias::Right:
		left = std::make_shared<AVLTree>(AVLTree(key, val, a, b, Bias::Equal));
		bias = Bias::Equal;
	}
	key = right->key; val = right->val;
	right = c;
}
void AVLTree::double_right() {
	const auto a = left->left;
	const auto b = left->right->left;
	const auto c = left->right->right;
	const auto d = right;
	switch (left->right->bias) {
	case Bias::Equal:
		right = std::make_shared<AVLTree>(AVLTree(key, val, c, d, Bias::Equal));
		left->bias = Bias::Equal;
		break;
	case Bias::Right:
		right = std::make_shared<AVLTree>(AVLTree(key, val, c, d, Bias::Equal));
		left->bias = Bias::Left;
		break;
	case Bias::Left:
		right = std::make_shared<AVLTree>(AVLTree(key, val, c, d, Bias::Right));
		left->bias = Bias::Equal;
	}
	val = left->right->val; key = left->right->key;
	left->right = b;
	bias = Bias::Equal;
}
void AVLTree::double_left() {
	const auto a = left;
	const auto b = right->left->left;
	const auto c = right->left->right;
	const auto d = right->right;
	switch (right->left->bias) {
	case Bias::Equal:
		left = std::make_shared<AVLTree>(AVLTree(key, val, a, b, Bias::Equal));
		right->bias = Bias::Equal;
		break;
	case Bias::Left:
		left = std::make_shared<AVLTree>(AVLTree(key, val, a, b, Bias::Equal));
		right->bias = Bias::Right;
		break;
	case Bias::Right:
		left = std::make_shared<AVLTree>(AVLTree(key, val, a, b, Bias::Left));
		right->bias = Bias::Equal;
	}
	val = right->left->val; key = right->left->key;
	right->left = c;
	bias = Bias::Equal;
}
bool AVLTree::increase_right() {
	switch (bias) {
	case Bias::Equal:
		bias = Bias::Right; return true; break;
	case Bias::Left:
		bias = Bias::Equal; return false; break;
	case Bias::Right:
		switch (right->bias) {
		case Bias::Equal: turn_left(); return true; break;
		case Bias::Left: double_left(); return false; break;
		case Bias::Right: turn_left(); return false;
		}
	}
}
bool AVLTree::increase_left() {
	switch (bias) {
	case Bias::Equal:
		bias = Bias::Left; return true; break;
	case Bias::Right:
		bias = Bias::Equal; return false; break;
	case Bias::Left:
		switch (left->bias) {
		case Bias::Equal: turn_right(); return true; break;
		case Bias::Right: double_right(); return false; break;
		case Bias::Left: turn_right(); return false;
		}
	}
}
void AVLTree::sub_map(const std::function<Value(const Value &)> &f) {
	val = f(val);
	if (left) left->sub_map(f);
	if (right) right->sub_map(f);
}
int main() {
	int n;
	std::cin >> n;
	AVLTree tree;
	for (; n > 0; --n) {
		int v;
		std::cin >> v;
		tree.incriment(v);
	}
	std::cout << tree.map([](const int &n) {return (n == 1) ? 1 : 0; }).sum() << std::endl;
	return 0;
}
0