fork(1) download
copy 
  1. #include<iostream>
  2. #include<string>
  3. #include<algorithm>
  4. #include<vector>
  5. #include<iterator>
  6.  
  7. using namespace std;
  8.  
  9. int Hash(const string & s, int mod = 101)
  10. {
  11. 	if (s.empty())
  12. 		return 0;
  13. 	int hash = 0, i = 1;
  14. 	for_each(begin(s), end(s), [&](const char & c)
  15. 	{
  16. 		hash += static_cast<int>(c) * i++;
  17. 	});
  18.  
  19. 	return (19 * hash) % mod;
  20. }
  21.  
  22. class HashTableOA
  23. {
  24. public:
  25. 	using HashBody = vector<string>;
  26.  
  27. 	HashTableOA() : size_(101), count_(0), body_(size_, "EMPTY") {}
  28.  
  29. 	void Insert(const string & str)
  30. 	{
  31. 		if (Find(str) != -1)
  32. 			return;
  33.  
  34. 		int id = 0;
  35. 		for (size_t i = 0; i < 20; ++i)
  36. 		{
  37. 			id = (Hash(str, size_) + i * i + 23 * i) % size_;
  38. 			if (body_[id] == "EMPTY" || body_[id] == "DELETED")
  39. 			{
  40. 				body_[id] = str;
  41. 				++count_;
  42. 				break;
  43. 			}
  44. 			// If element is already in hash table: ignore it
  45. 			else if (body_[id] == str)
  46. 				break;
  47. 		}
  48. 		// If i > 20 we assume that insertion operation could not be performed
  49. 	}
  50.  
  51. 	int Find(const string & str)
  52. 	{
  53. 		if (count_ == 0)
  54. 			return -1;
  55.  
  56. 		int id = 0;
  57. 		for (size_t i = 0; i < 20; ++i)
  58. 		{
  59. 			id = (Hash(str, size_) + i * i + 23 * i) % size_;
  60. 			if (body_[id] == "EMPTY")
  61. 				return -1;
  62. 			else if (body_[id] == str)
  63. 				return id;
  64. 		}
  65. 	}
  66.  
  67. 	void Remove(const string & str)
  68. 	{
  69. 		int id = Find(str);
  70. 		if (id == -1)
  71. 			return;
  72. 		body_[id] = "DELETED";
  73. 		--count_;
  74. 	}
  75.  
  76. 	friend ostream & operator<<(ostream & os, const HashTableOA & ht)
  77. 	{
  78. 		os << ht.count_ << endl;
  79. 		for (auto it = begin(ht.body_); it != end(ht.body_); ++it)
  80. 			if (*it != "EMPTY" && *it != "DELETED")
  81. 				os << distance(begin(ht.body_), it) << ":" << *it << endl;
  82. 		return os;
  83. 	}
  84.  
  85. private:
  86. 	size_t size_;
  87. 	size_t count_;
  88. 	HashBody body_;
  89. };
  90.  
  91. int main()
  92. {
  93. 	size_t task_num; cin >> task_num;
  94. 	for (size_t i = 0; i < task_num; ++i)
  95. 	{
  96. 		size_t op_num; cin >> op_num;
  97. 		string tmp; getline(cin, tmp);
  98. 		HashTableOA ht;
  99. 		for (size_t j = 0; j < op_num; ++j)
  100. 		{
  101. 			string line; getline(cin, line);
  102. 			string str(next(find(begin(line), end(line), ':')), end(line));
  103. 			if (*begin(line) == 'A')
  104. 				ht.Insert(str);
  105. 			else
  106. 				ht.Remove(str);
  107. 		}
  108. 		cout << ht;
  109. 	}
  110.  
  111. 	return 0;
  112. }
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
1
3
ADD:aac
ADD:aace
DEL:aac
stdout
copy 
1
86:aace
https://ideone.com/FwuSpI
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!