#81976 (C++11) No.182 新規性の虜

提出ソース

結果

問題	No.182 新規性の虜
ユーザー	yudedako
提出日時	2016-03-15 19:49:52
言語	C++11 (gcc 11.4.0)
結果	TLE
実行時間	-
コード長	5,119 bytes
コンパイル時間	1,158 ms
コンパイル使用メモリ	76,348 KB
実行使用メモリ	13,640 KB
最終ジャッジ日時	2024-10-01 07:01:48
合計ジャッジ時間	8,499 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,632 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	1 ms 6,816 KB
testcase_03	AC	1 ms 6,816 KB
testcase_04	AC	1 ms 6,816 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	1 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	44 ms 7,296 KB
testcase_09	AC	75 ms 9,984 KB
testcase_10	AC	63 ms 9,088 KB
testcase_11	AC	51 ms 8,064 KB
testcase_12	AC	20 ms 6,816 KB
testcase_13	AC	1 ms 6,820 KB
testcase_14	AC	1 ms 6,816 KB
testcase_15	AC	1 ms 6,816 KB
testcase_16	AC	1 ms 6,820 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	30 ms 6,820 KB
testcase_19	AC	23 ms 6,816 KB
testcase_20	AC	16 ms 6,820 KB
testcase_21	AC	35 ms 6,816 KB
testcase_22	AC	18 ms 6,816 KB
testcase_23	AC	1 ms 6,816 KB
testcase_24	TLE	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
evil01.txt	--	-
evil02.txt	--	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In member function ‘bool AVLTree::increase_right()’:
main.cpp:153:1: warning: control reaches end of non-void function [-Wreturn-type]
  153 | }
      | ^
main.cpp: In member function ‘bool AVLTree::increase_left()’:
main.cpp:167:1: warning: control reaches end of non-void function [-Wreturn-type]
  167 | }
      | ^

ソースコード

raw source code

#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 &)> &);
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;
}
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 false; 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 false; 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;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード