結果

問題 No.182 新規性の虜
コンテスト
ユーザー yudedako
提出日時 2016-03-25 14:04:09
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 6,805 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 537 ms
コンパイル使用メモリ 63,040 KB
実行使用メモリ 13,480 KB
最終ジャッジ日時 2024-10-02 00:48:37
合計ジャッジ時間 8,153 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 TLE * 1 -- * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 | }
      | ^

ソースコード

diff #
raw source code 

#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;
}
0