blob: 8af47d29038e267f4758bb929b982173bf4c09c4 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using std::string;
using std::vector;
using std::cin;
struct Query {
string type, s;
size_t ind;
};
class QueryProcessor {
int bucket_count;
// store all strings in one vector
vector<string> elems;
size_t hash_func(const string& s) const {
static const size_t multiplier = 263;
static const size_t prime = 1000000007;
unsigned long long hash = 0;
for (int i = static_cast<int> (s.size()) - 1; i >= 0; --i)
hash = (hash * multiplier + s[i]) % prime;
return hash % bucket_count;
}
public:
explicit QueryProcessor(int bucket_count): bucket_count(bucket_count) {}
Query readQuery() const {
Query query;
cin >> query.type;
if (query.type != "check")
cin >> query.s;
else
cin >> query.ind;
return query;
}
void writeSearchResult(bool was_found) const {
std::cout << (was_found ? "yes\n" : "no\n");
}
void processQuery(const Query& query) {
if (query.type == "check") {
// use reverse order, because we append strings to the end
for (int i = static_cast<int>(elems.size()) - 1; i >= 0; --i)
if (hash_func(elems[i]) == query.ind)
std::cout << elems[i] << " ";
std::cout << "\n";
} else {
vector<string>::iterator it = std::find(elems.begin(), elems.end(), query.s);
if (query.type == "find")
writeSearchResult(it != elems.end());
else if (query.type == "add") {
if (it == elems.end())
elems.push_back(query.s);
} else if (query.type == "del") {
if (it != elems.end())
elems.erase(it);
}
}
}
void processQueries() {
int n;
cin >> n;
for (int i = 0; i < n; ++i)
processQuery(readQuery());
}
};
int main() {
std::ios_base::sync_with_stdio(false);
int bucket_count;
cin >> bucket_count;
QueryProcessor proc(bucket_count);
proc.processQueries();
return 0;
}
|
