Good morning everyone!!
I have tested all possible cases about HASHIT task and still getting the wrong answer! Could anyone help me to find the bug in my code. Code itself is listed below.
Link to code output on the example task.
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iterator>
using namespace std;
int Hash(const string & s, int mod = 101)
{
if (s.empty())
return 0;
int hash = 0, i = 1;
for_each(begin(s), end(s), [&](const char & c)
{
hash += static_cast<int>(c) * i++;
});
return (19 * hash) % mod;
}
class HashTableOA
{
public:
using HashBody = vector<string>;
HashTableOA() : size_(101), count_(0), body_(size_, "EMPTY") {}
void Insert(const string & str)
{
if (Find(str) != -1)
return;
int id = 0;
for (size_t i = 0; i < 20; ++i)
{
id = (Hash(str, size_) + i * i + 23 * i) % size_;
if (body_[id] == "EMPTY" || body_[id] == "DELETED")
{
body_[id] = str;
++count_;
break;
}
// If element is already in hash table: ignore it
else if (body_[id] == str)
break;
}
// If i > 20 we assume that insertion operation could not be performed
}
int Find(const string & str)
{
if (count_ == 0)
return -1;
int id = 0;
for (size_t i = 0; i < 20; ++i)
{
id = (Hash(str, size_) + i * i + 23 * i) % size_;
if (body_[id] == "EMPTY")
return -1;
else if (body_[id] == str)
return id;
}
}
void Remove(const string & str)
{
int id = Find(str);
if (id == -1)
return;
body_[id] = "DELETED";
--count_;
}
friend ostream & operator<<(ostream & os, const HashTableOA & ht)
{
os << ht.count_ << endl;
for (auto it = begin(ht.body_); it != end(ht.body_); ++it)
if (*it != "EMPTY" && *it != "DELETED")
os << distance(begin(ht.body_), it) << ":" << *it << endl;
return os;
}
private:
size_t size_;
size_t count_;
HashBody body_;
};
int main()
{
size_t task_num; cin >> task_num;
for (size_t i = 0; i < task_num; ++i)
{
size_t op_num; cin >> op_num;
string tmp; getline(cin, tmp);
HashTableOA ht;
for (size_t j = 0; j < op_num; ++j)
{
string line; getline(cin, line);
string str(next(find(begin(line), end(line), ':')), end(line));
if (*begin(line) == 'A')
ht.Insert(str);
else
ht.Remove(str);
}
cout << ht;
}
return 0;
}