結果

問題 No.182 新規性の虜
ユーザー yudedakoyudedako
提出日時 2016-03-15 20:19:01
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 5,291 bytes
コンパイル時間 943 ms
コンパイル使用メモリ 75,788 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-10-01 07:02:10
合計ジャッジ時間 4,245 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 WA -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 WA -
testcase_15 AC 2 ms
6,820 KB
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 AC 2 ms
6,816 KB
testcase_24 WA -
testcase_25 AC 15 ms
6,820 KB
testcase_26 RE -
testcase_27 WA -
evil01.txt WA -
evil02.txt WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘bool AVLTree::increase_right()’:
main.cpp:160:1: warning: control reaches end of non-void function [-Wreturn-type]
  160 | }
      | ^
main.cpp: In member function ‘bool AVLTree::increase_left()’:
main.cpp:174:1: warning: control reaches end of non-void function [-Wreturn-type]
  174 | }
      | ^

ソースコード

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;
private:
	std::shared_ptr<AVLTree> left, right;
	Key key;
	Value val;
	Bias bias;
	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;
}
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 = left->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 = left->right->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