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

• 問題: No.182 新規性の虜
• ユーザー: yudedako
• 提出日時: 2016-03-25 14:04:09
• 言語: C++11 (gcc 11.4.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,805 bytes
• コンパイル時間: 537 ms
• コンパイル使用メモリ: 63,040 KB
• 実行使用メモリ: 13,480 KB
• 最終ジャッジ日時: 2024-10-02 00:48:37
• 合計ジャッジ時間: 8,153 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,820 KB
testcase_01	AC	2 ms; 6,820 KB
testcase_02	AC	2 ms; 6,816 KB
testcase_03	AC	2 ms; 6,816 KB
testcase_04	AC	1 ms; 6,820 KB
testcase_05	AC	2 ms; 6,816 KB
testcase_06	AC	2 ms; 6,816 KB
testcase_07	AC	2 ms; 6,816 KB
testcase_08	AC	64 ms; 6,816 KB
testcase_09	AC	117 ms; 7,424 KB
testcase_10	AC	98 ms; 6,948 KB
testcase_11	AC	80 ms; 6,820 KB
testcase_12	AC	31 ms; 6,816 KB
testcase_13	AC	1 ms; 6,816 KB
testcase_14	AC	2 ms; 6,820 KB
testcase_15	AC	2 ms; 6,820 KB
testcase_16	AC	2 ms; 6,816 KB
testcase_17	AC	1 ms; 6,816 KB
testcase_18	AC	59 ms; 6,820 KB
testcase_19	AC	43 ms; 6,820 KB
testcase_20	AC	26 ms; 6,816 KB
testcase_21	AC	66 ms; 6,816 KB
testcase_22	AC	33 ms; 6,816 KB
testcase_23	AC	1 ms; 6,820 KB
testcase_24	TLE	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
evil01.txt	--	-
evil02.txt	--	-

コンパイルメッセージ

main.cpp: In member function ‘bool AVLTree<K, V>::insert_by_key(const K&, const V&, AVLTree<K, V>::Tree*&) [with K = int; V = bool]’:
main.cpp:161:1: warning: control reaches end of non-void function [-Wreturn-type]
  161 | }
      | ^

ソースコード

#include <cassert>
#include <iostream>
#include <vector>
template<typename K, typename V>
class AVLTree {
	enum class Bias :char {
		L, Eq, R
	};
	struct Tree {
		V val;
		Tree *left{ nullptr }, *right{ nullptr };
		K key;
		Bias bias{ Bias::Eq };
		Tree(const K &, const V &);
		~Tree();
		bool has_key(const K &) const;
		V &operator[](const K &);
		Tree* find_leften() const;
	};
public:
	AVLTree();
	~AVLTree();
	void insert(const K &, const V &);
	void erase(const K &);
	bool has_key(const K &) const;
	size_t size() const;
	V &operator[](const K &);
private:
	int factor_size{ 0 };
	Tree* tree{ nullptr };
	bool turn_right(Tree* &top);
	bool turn_left(Tree* &top);
	bool double_right(Tree* &top);
	bool double_left(Tree* &top);
	bool insert_by_key(const K &, const V &, Tree* &);
	bool increase_right(Tree* &);
	bool increase_left(Tree* &);
	bool reduce_right(Tree* &);
	bool reduce_left(Tree* &);
	bool erase_by_key(const K &, Tree* &);
	bool void_leften(Tree* &);
	void move_position(Tree* &from, Tree* &to);
};

template<typename K, typename V>
AVLTree<K, V>::AVLTree() {};
template<typename K, typename V>
AVLTree<K, V>::~AVLTree() { delete tree; };

template<typename K, typename V>
void AVLTree<K, V>::insert(const K &k, const V &v) {
	if (factor_size++ > 0) insert_by_key(k, v, tree);
	else tree = new Tree(k, v);
}
template<typename K, typename V>
void AVLTree<K, V>::erase(const K &k) {
	assert(factor_size > 0 && tree->has_key(k));
	erase_by_key(k, tree);
	--factor_size;
}
template<typename K, typename V>
bool AVLTree<K, V>::has_key(const K &k) const {
	return factor_size > 0 && tree->has_key(k);
}
template<typename K, typename V>
V &AVLTree<K, V>::operator[](const K &k) {
	assert(factor_size > 0 && tree->has_key(k));
	return tree->operator[](k);
}
template<typename K, typename V>
size_t AVLTree<K, V>::size() const {
	return factor_size;
}

template<typename K, typename V>
AVLTree<K, V>::Tree::Tree(const K &k, const V &v) :key{ k }, val{ v } {};
template<typename K, typename V>
AVLTree<K, V>::Tree::~Tree() {
	delete left;
	delete right;
}
template<typename K, typename V>
bool AVLTree<K, V>::Tree::has_key(const K &k) const {
	if (k == key) return true;
	else if (k < key && left) return left->has_key(k);
	else if (k > key && right) return right->has_key(k);
	else return false;
}
template<typename K, typename V>
V &AVLTree<K, V>::Tree::operator[](const K &k) {
	if (k == key) return val;
	else if (k < key && left) return left->operator[](k);
	else if (k > key && right) return right->operator[](k);
	else assert(false);
}
template<typename K, typename V>
typename AVLTree<K, V>::Tree* AVLTree<K, V>::Tree::find_leften() const {
	if (left) return left->find_leften();
	else return this;
}

template<typename K, typename V>
bool AVLTree<K, V>::turn_right(AVLTree<K, V>::Tree* &top) {
	auto const old_left = top->left;
	top->left = top->left->right;
	old_left->right = top;
	top = old_left;
	switch (old_left->bias) {
	case Bias::Eq:
		top->bias = Bias::R; top->right->bias = Bias::L; return true;
	case Bias::L:
		top->bias = Bias::Eq; top->right->bias = Bias::Eq; return false;
	default: assert(false);
	}
};
template<typename K, typename V>
bool AVLTree<K, V>::turn_left(AVLTree<K, V>::Tree* &top) {
	auto const old_right = top->right;
	top->right = top->right->left;
	old_right->left = top;
	top = old_right;
	switch (old_right->bias) {
	case Bias::Eq:
		top->bias = Bias::L; top->left->bias = Bias::R; return true;
	case Bias::R:
		top->bias = Bias::Eq; top->left->bias = Bias::Eq; return false;
	default: assert(false);
	}
};
template<typename K, typename V>
bool AVLTree<K, V>::double_right(AVLTree<K, V>::Tree* &top) {
	turn_left(top->left);
	turn_right(top);
	return false;
};
template<typename K, typename V>
bool AVLTree<K, V>::double_left(AVLTree<K, V>::Tree* &top) {
	turn_right(top->right);
	turn_left(top);
	return false;
};
template<typename K, typename V>
bool AVLTree<K, V>::insert_by_key(const K &k, const V &v, AVLTree<K, V>::Tree* &top) {
	assert(top->key != k);
	if (k < top->key) {
		if (!top->left || insert_by_key(k, v, top->left)) {
			if (!top->left) top->left = new Tree(k, v);
			return  increase_left(top);
		}
		else return false;
	}
	else {
		if (!top->right || insert_by_key(k, v, top->right)) {
			if (!top->right || insert_by_key(k, v, top->right)) {
				if (!top->right) top->right = new Tree(k, v);
				return increase_right(top);
			}
		}
		else return false;
	}
}
template<typename K, typename V>
bool AVLTree<K, V>::increase_right(AVLTree<K, V>::Tree* &top) {
	if (top->bias == Bias::R) {
		switch (top->right->bias) {
		case Bias::L: return double_left(top);
		default: return turn_left(top);
		}
	}
	else return false;
}
template<typename K, typename V>
bool AVLTree<K, V>::increase_left(AVLTree<K, V>::Tree* &top) {
	if (top->bias == Bias::L) {
		switch (top->left->bias) {
		case Bias::R: return double_right(top);
		default: return turn_right(top);
		}
	}
	else return false;
}
template<typename K, typename V>
bool AVLTree<K, V>::reduce_right(AVLTree<K, V>::Tree* &top) {
	return !increase_left(top);
}
template<typename K, typename V>
bool AVLTree<K, V>::reduce_left(AVLTree<K, V>::Tree* &top) {
	return !increase_right(top);
}
template<typename K, typename V>
bool AVLTree<K, V>::erase_by_key(const K &k, AVLTree<K, V>::Tree* &top) {
	if (k == top->key) {
		if (top->right) {
			auto leften = top->right->find_leften();
			auto flag = void_leften(top->right);
			assert(!leften->left);
			move_position(leften, top);
			if (flag) return reduce_right(top);
			else return false;
		}
		else {
			if (top->left) move_position(top->left, top);
			else {
				delete top;
				top = nullptr;
			}
			return true;
		}
	}
	else if (k < top->key) {
		assert(top->left);
		if (erase_by_key(k, top->left)) return reduce_left(top);
		else return false;
	}
	else {
		assert(top->right);
		if (erase_by_key(k, top->right))  return reduce_right(top);
		else return false;
	}
}
template<typename K, typename V>
bool AVLTree<K, V>::void_leften(AVLTree<K, V>::Tree* &top) {
	if (top->left) {
		if (void_leften(top->left)) return reduce_left(top);
		else return false;
	}
	else {
		if (top->right) top = top->right;
		else top = nullptr;
		return true;
	}
}
template<typename K, typename V>
void AVLTree<K, V>::move_position(AVLTree<K, V>::Tree* &from, AVLTree<K, V>::Tree* &to) {
	from->left = to->left;
	from->right = to->right;
	auto temp = to;
	to = from;
	temp->left = nullptr;
	temp->right = nullptr;
	delete temp;
}

int main() {
	int n;
	std::cin >> n;
	std::vector<int> vector(n);
	AVLTree<int, bool> tree;
	for (auto &v : vector) {
		std::cin >> v;
		if (tree.has_key(v)) tree[v] = false;
		else tree.insert(v, true);
	}
	int sum = 0;
	for (const auto &v : vector) {
		if (tree[v]) ++sum;
	}
	std::cout << sum << std::endl;
	return 0;
}