結果

問題 No.182 新規性の虜
コンテスト
ユーザー yudedako
提出日時 2016-03-24 20:30:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 5,518 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,296 ms
コンパイル使用メモリ 88,848 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2024-10-02 00:14:11
合計ジャッジ時間 6,017 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 RE * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘bool AVLTree::increase_right()’:
main.cpp:132:1: warning: control reaches end of non-void function [-Wreturn-type]
  132 | }
      | ^
main.cpp: In member function ‘bool AVLTree::increase_left()’:
main.cpp:146:1: warning: control reaches end of non-void function [-Wreturn-type]
  146 | }
      | ^

ソースコード

diff #
raw source code 

#include <memory>
#include <iostream>
#include <vector>
class AVLTree {
	enum class Bias : char {
		Left, Right, Equal
	};
	using Key = int;
	using Value = bool;
public:
	AVLTree(const Key &, const Value & = Value{}, std::unique_ptr<AVLTree> && = { nullptr }, std::unique_ptr<AVLTree> && = { nullptr }, const Bias & = Bias::Equal);
	AVLTree();
	void insert(const Key &, const Value &);
	Value &operator[](const Key &);
	bool has_key(const Key &) const;
	void erase(const Key &);
private:
	Value val;
	std::unique_ptr<AVLTree> left, right;
	Key key;
	Bias bias;
	bool initialized;
	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();
	bool reduce_right();
	bool reduce_left();
	const AVLTree* leften() const;
	bool erase_leften();
	bool sub_erase(const Key &);
	bool is_not_leaf() const;
};
AVLTree::AVLTree(const Key &k, const Value &v, std::unique_ptr<AVLTree> &&l, std::unique_ptr<AVLTree> &&r, const Bias &b) :key{ k }, val{ v }, left{ std::move(l) }, right{ std::move(r) }, bias{ b }, initialized{ true } {};
AVLTree::AVLTree() :key{}, val{}, left{ nullptr }, right{ nullptr }, bias{ Bias::Equal }, initialized{ false } {};
void AVLTree::insert(const Key &k, const Value &v) {
	if (initialized) sub_insert(k, v);
	else {
		key = k; val = v; initialized = true;
	}
}
AVLTree::Value &AVLTree::operator[](const Key &k) {
	if (k == key) {
		return val;
	}
	else if (k < key) {
		return left->operator[](k);
	}
	else {
		return right->operator[](k);
	}
}
bool AVLTree::has_key(const Key &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);
	return false;
}
void AVLTree::erase(const Key &k) {
	if (initialized) {
		if (k == key) initialized = false;
		else sub_erase(k);
	}
}
bool AVLTree::sub_insert(const Key &k, const Value &v) {
	if (k < key) {
		if (!left || left->sub_insert(k, v)) {
			if (!left) left = std::unique_ptr<AVLTree>(new AVLTree(k, v));
			return increase_left();
		}
		else return false;
	}
	else if (k > key) {
		if (!right || right->sub_insert(k, v)) {
			if (!right) right = std::unique_ptr<AVLTree>(new AVLTree(k, v));
			return increase_right();
		}
		else return false;
	}
	return false;
}
void AVLTree::turn_right() {
	switch (left->bias) {
	case Bias::Equal:
		right = std::unique_ptr<AVLTree>(new AVLTree(key, val, std::move(left->right), std::move(right), Bias::Left));
		bias = Bias::Right;
		break;
	case Bias::Left:
		right = std::unique_ptr<AVLTree>(new AVLTree(key, val, std::move(left->right), std::move(right), Bias::Equal));
		bias = Bias::Equal;
	}
	key = left->key; val = left->val;
	left = std::move(left->left);
}
void AVLTree::turn_left() {
	switch (right->bias) {
	case Bias::Equal:
		left = std::unique_ptr<AVLTree>(new AVLTree(key, val, std::move(left), std::move(right->left), Bias::Right));
		bias = Bias::Left;
		break;
	case Bias::Right:
		left = std::unique_ptr<AVLTree>(new AVLTree(key, val, std::move(left), std::move(right->left), Bias::Equal));
		bias = Bias::Equal;
	}
	key = right->key; val = right->val;
	right = std::move(right->right);
}
void AVLTree::double_right() {
	left->turn_left();
	turn_right();
}
void AVLTree::double_left() {
	right->turn_right();
	turn_left();
}
bool AVLTree::increase_right() {
	switch (bias) {
	case Bias::Equal:
		bias = Bias::Right; return true; 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 true; 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;
		}
	}
}
bool AVLTree::reduce_right() {
	return !increase_left();
}
bool AVLTree::reduce_left() {
	return !increase_right();
}
const AVLTree* AVLTree::leften() const {
	if (left) return left->leften();
	else return this;
}
bool AVLTree::erase_leften() {
	if (left->left) {
		if (left->erase_leften()) return reduce_left();
		else return false;
	}
	else {
		left = std::move(left->right);
		return true;
	}
}
bool AVLTree::sub_erase(const Key &k) {
	if (k < key) {
		if (left->is_not_leaf()) {
			if (left->sub_erase(k)) return reduce_left();
			else return false;
		}
		else {
			left.reset();
			return bool(right);
		}
	}
	else if (k > key) {
		if (right->is_not_leaf()) {
			if (right->sub_erase(k)) return reduce_right();
			else return false;
		}
		else {
			right.reset();
			return bool(left);
		}
	}
	else {
		if (right) {
			auto l = right->leften();
			val = l->val; key = l->key;
			if (right->erase_leften()) return reduce_right();
			else return false;
		}
		else {
			*this = std::move(*left);
			return true;
		}
	}
};
bool AVLTree::is_not_leaf() const {
	return right || left;
}

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