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

提出ソース

結果

問題	No.182 新規性の虜
ユーザー	yudedako
提出日時	2016-03-24 20:30:00
言語	C++11 (gcc 11.4.0)
結果	RE
実行時間	-
コード長	5,518 bytes
コンパイル時間	965 ms
コンパイル使用メモリ	88,412 KB
実行使用メモリ	8,192 KB
最終ジャッジ日時	2024-04-09 23:34:02
合計ジャッジ時間	4,731 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	RE	-
testcase_06	AC	1 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	1 ms 6,940 KB
testcase_14	RE	-
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	1 ms 6,940 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	62 ms 8,192 KB
testcase_25	AC	16 ms 6,944 KB
testcase_26	RE	-
testcase_27	AC	2 ms 6,944 KB
evil01.txt	AC	72 ms 8,192 KB
evil02.txt	AC	72 ms 8,192 KB

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

コンパイルメッセージ

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 | }
      | ^

ソースコード

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード