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

提出ソース

結果

問題	No.182 新規性の虜
ユーザー	yudedako
提出日時	2016-03-25 16:16:56
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	98 ms / 5,000 ms
コード長	8,630 bytes
コンパイル時間	1,007 ms
コンパイル使用メモリ	61,544 KB
実行使用メモリ	8,448 KB
最終ジャッジ日時	2024-06-08 06:03:13
合計ジャッジ時間	2,823 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	55 ms 5,812 KB
testcase_09	AC	98 ms 7,472 KB
testcase_10	AC	83 ms 6,820 KB
testcase_11	AC	64 ms 6,344 KB
testcase_12	AC	26 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	1 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	49 ms 5,376 KB
testcase_19	AC	36 ms 5,376 KB
testcase_20	AC	24 ms 5,376 KB
testcase_21	AC	58 ms 5,376 KB
testcase_22	AC	28 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	68 ms 8,448 KB
testcase_25	AC	16 ms 5,376 KB
testcase_26	AC	11 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
evil01.txt	AC	79 ms 8,320 KB
evil02.txt	AC	81 ms 8,192 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 single_right(Tree* &top);
	bool single_left(Tree* &top);
	void turn_right(Tree* &top);
	void 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>
void 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;
};
template<typename K, typename V>
void 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;
};

template<typename K, typename V>
bool AVLTree<K, V>::single_right(Tree *&top) {
	turn_right(top);
	switch (top->bias) {
	case Bias::L:
		top->bias = Bias::Eq; top->right->bias = Bias::Eq; return false;
	case Bias::Eq:
		top->bias = Bias::R; top->right->bias = Bias::L; return true;
	default: assert(false);
	}
}
template<typename K, typename V>
bool AVLTree<K, V>::single_left(Tree *&top) {
	turn_left(top);
	switch (top->bias) {
	case Bias::R:
		top->bias = Bias::Eq; top->left->bias = Bias::Eq; return false;
	case Bias::Eq:
		top->bias = Bias::L; top->left->bias = Bias::R; return true;
	default: assert(false);
	}
}
template<typename K, typename V>
bool AVLTree<K, V>::double_right(Tree* &top) {
	turn_left(top->left);
	turn_right(top);
	switch (top->bias) {
	case Bias::Eq:
		top->bias = Bias::Eq; top->left->bias = Bias::Eq; top->right->bias = Bias::Eq; return false;
	case Bias::R:
		top->bias = Bias::Eq; top->left->bias = Bias::L; top->right->bias = Bias::Eq; return false;
	case Bias::L:
		top->bias = Bias::Eq; top->left->bias = Bias::Eq; top->right->bias = Bias::R; return false;
	default: assert(false);
	}
};
template<typename K, typename V>
bool AVLTree<K, V>::double_left(Tree* &top) {
	turn_right(top->right);
	turn_left(top);
	switch (top->bias) {
	case Bias::Eq:
		top->bias = Bias::Eq; top->left->bias = Bias::Eq; top->right->bias = Bias::Eq; return false;
	case Bias::L:
		top->bias = Bias::Eq; top->left->bias = Bias::Eq; top->right->bias = Bias::R; return false;
	case Bias::R:
		top->bias = Bias::Eq; top->left->bias = Bias::L; top->right->bias = Bias::Eq; return false;
	default: assert(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 single_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 single_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;
	from->bias = to->bias;
	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

結果

テストケース

ソースコード