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

提出ソース

結果

問題	No.182 新規性の虜
ユーザー	yudedako
提出日時	2016-03-25 14:39:11
言語	C++11 (gcc 11.4.0)
結果	RE
実行時間	-
コード長	7,623 bytes
コンパイル時間	682 ms
コンパイル使用メモリ	63,000 KB
実行使用メモリ	8,192 KB
最終ジャッジ日時	2024-04-09 23:51:58
合計ジャッジ時間	3,102 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	RE	-
testcase_06	AC	2 ms 6,940 KB
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	AC	2 ms 6,944 KB
testcase_14	RE	-
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	1 ms 6,944 KB
testcase_17	AC	1 ms 6,944 KB
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	AC	1 ms 6,940 KB
testcase_24	AC	68 ms 8,192 KB
testcase_25	AC	16 ms 6,940 KB
testcase_26	RE	-
testcase_27	AC	2 ms 6,940 KB
evil01.txt	AC	82 ms 8,192 KB
evil02.txt	AC	80 ms 8,448 KB

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

ソースコード

raw source code

#include <cassert>
#include <iostream>
#include <vector>
template<typename K, typename V>
class AVLTree {
	enum class Bias :char {
		L = 'L', Eq = 'E', R = '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;
		int depth() const;
		void show() const;
	};
public:
	AVLTree();
	~AVLTree();
	void insert(const K &, const V &);
	void erase(const K &);
	bool has_key(const K &) const;
	size_t size() const;
	int depth() const;
	void show_all() 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>
int AVLTree<K, V>::depth() const {
	if (factor_size == 0) return 0;
	else return tree->depth();
}
template<typename K, typename V>
int AVLTree<K, V>::Tree::depth() const {
	if (left && right) {
		switch (bias) {
		case Bias::Eq:
		case Bias::R: return right->depth() + 1;
		case Bias::L: return left->depth() + 1;
		}
	}
	else {
		if (bias == Bias::Eq) return 1;
		else return 2;
	}
}
template<typename K, typename V>
void AVLTree<K, V>::show_all() const {
	if (factor_size == 0) std::cout << "null\n";
	else tree->show();
}
template<typename K, typename V>
void AVLTree<K, V>::Tree::show() const {
	std::cout << '[' << key << ',' << val << "] ";
	if (left) left->show();
	if (right) right->show();
}

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(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(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(Tree* &top) {
	turn_left(top->left);
	turn_right(top);
	return false;
};
template<typename K, typename V>
bool AVLTree<K, V>::double_left(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, 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) top->right = new Tree(k, v);
			return increase_right(top);
		}
		else return false;
	}
}
template<typename K, typename V>
bool AVLTree<K, V>::increase_right(Tree* &top) {
	switch (top->bias) {
	case Bias::R:
		switch (top->right->bias) {
		case Bias::L: return double_left(top);
		default: return turn_left(top);
		}
	case Bias::Eq:
		top->bias = Bias::R; return true;
	case Bias::L:
		top->bias = Bias::Eq; return false;
	default: assert(false);
	}
}
template<typename K, typename V>
bool AVLTree<K, V>::increase_left(Tree* &top) {
	switch (top->bias) {
	case Bias::L:
		switch (top->left->bias) {
		case Bias::R: return double_right(top);
		default: return turn_right(top);
		}
	case Bias::Eq:
		top->bias = Bias::L; return true;
	case Bias::R:
		top->bias = Bias::Eq; return false;
	default: assert(false);
	}
}
template<typename K, typename V>
bool AVLTree<K, V>::reduce_right(Tree* &top) {
	return !increase_left(top);
}
template<typename K, typename V>
bool AVLTree<K, V>::reduce_left(Tree* &top) {
	return !increase_right(top);
}
template<typename K, typename V>
bool AVLTree<K, V>::erase_by_key(const K &k, 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(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(Tree* &from, 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;
}

yukicoder

結果

テストケース

ソースコード