diff options
| -rw-r--r-- | Sources/DataStructure.cpp | 246 |
1 files changed, 71 insertions, 175 deletions
diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp index 07f8b43..064ca45 100644 --- a/Sources/DataStructure.cpp +++ b/Sources/DataStructure.cpp @@ -1,190 +1,86 @@ #include <iostream> -#include <vector> #include <string> +#include <vector> +#include <algorithm> using std::string; using std::vector; using std::cin; struct Query { - string type, name; - int number; + string type, s; + size_t ind; }; -vector<Query> read_queries() { - int n; - cin >> n; - vector<Query> queries(n); - for (int i = 0; i < n; ++i) { - cin >> queries[i].type; - if (queries[i].type == "add") - cin >> queries[i].number >> queries[i].name; - else - cin >> queries[i].number; - } - return queries; -} +class QueryProcessor { + int bucket_count; + // store all strings in one vector + 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; + } -void write_responses(const vector<string>& result) { - for (size_t i = 0; i < result.size(); ++i) - std::cout << result[i] << "\n"; -} +public: + explicit QueryProcessor(int bucket_count) : + bucket_count(bucket_count) { + } -vector<string> process_queries(const vector<Query>& queries) { - vector<string> result; - // Keep list of all existing (i.e. not deleted yet) contacts. - vector<string> contacts(10000000); - for (size_t i = 0; i < contacts.size(); i++) { - contacts[i] = "not found"; - } - for (size_t i = 0; i < queries.size(); ++i) - if (queries[i].type == "add") { - contacts[queries[i].number] = queries[i].name; - } else if (queries[i].type == "del") { - contacts[queries[i].number] = "not found"; - } else { - result.push_back(contacts[queries[i].number]); - } - return result; -} + 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[query.ind].size()) - 1; i >= 0; + --i) + std::cout << elems[query.ind][i] << " "; + std::cout << "\n"; + } else { + int hashIndex = hash_func(query.s); + vector<string>::iterator it = std::find(elems[hashIndex].begin(), elems[hashIndex].end(), + query.s); + if (query.type == "find") + writeSearchResult(it != elems[hashIndex].end()); + else if (query.type == "add") { + if (it == elems[hashIndex].end()) + elems[hashIndex].push_back(query.s); + } else if (query.type == "del") { + if (it != elems[hashIndex].end()) + elems[hashIndex].erase(it); + } + } + } + + void processQueries() { + int n; + cin >> n; + elems.resize(n); + for (int i = 0; i < n; ++i) + processQuery(readQuery()); + } +}; int main() { - write_responses(process_queries(read_queries())); - return 0; + std::ios_base::sync_with_stdio(false); + int bucket_count; + cin >> bucket_count; + QueryProcessor proc(bucket_count); + proc.processQueries(); + return 0; } - -//#include <cstdio> -//#include <cstdlib> -//#include <vector> -//#include <algorithm> -//#include <iostream> -////#include <gtest/gtest.h> -// -//using std::cin; -//using std::cout; -//using std::endl; -//using std::max; -//using std::vector; -// -//struct Table { -// int numberOfRows; -// int setID; -// -// Table(int numberOfRows, int setID) : -// numberOfRows(numberOfRows), setID(setID) { -// } -//}; -// -//int maximumNumberOfRows = -1; -//vector<int> parent; -//vector<int> rank; -//vector<Table> tables; -// -//int find(int i) { -// if (i != parent[i]) -// parent[i] = find(parent[i]); -// return parent[i]; -//} -// -//void unite(int destination, int source) { -// int destination_id = find(destination); -// int source_id = find(source); -// if (destination_id == source_id) -// return; -// if (rank[destination_id] > rank[source_id]) -// parent[source_id] = destination_id; -// else { -// parent[destination_id] = source_id; -// if (rank[destination_id] == rank[source_id]) -// rank[source_id] = rank[source_id] + 1; -// } -//} -// -//void merge(int destination, int source) { -// int d = find(destination); -// int s = find(source); -// Table* realDestination = &tables[d]; -// Table* realSource = &tables[s]; -// if (d == s) { -// return; -// } -// maximumNumberOfRows = max(maximumNumberOfRows, -// tables[realDestination->setID].numberOfRows + tables[realSource->setID].numberOfRows); -// realDestination->numberOfRows = tables[realDestination->setID].numberOfRows -// + tables[realSource->setID].numberOfRows; -// realSource->numberOfRows = 0; -// realSource->setID = d; -// realDestination->setID = d; -// unite(destination, source); -//} -// -//int main() { -// int n, m; -// cin >> n >> m; -// -// parent.resize(n); -// rank.resize(n); -//// tables.resize(n); -// for (int i = 0; i < n; i++) { -// int numberOfRows; -// cin >> numberOfRows; -// tables.push_back(Table(numberOfRows, i)); -//// tables[i] = Table(numberOfRows, i); -// parent[i] = i; -// rank[i] = 0; -// maximumNumberOfRows = max(maximumNumberOfRows, numberOfRows); -// } -// -// for (int i = 0; i < m; i++) { -// int destination, source; -// cin >> destination >> source; -// --destination; -// --source; -// -// merge(destination, source); -// cout << maximumNumberOfRows << endl; -// } -// -// return 0; -//} -// -////TEST(MergingTables, t) { -//// maximumNumberOfRows = 1; -//// rank = {0, 0, 0, 0, 0}; -//// parent = {0, 1, 2, 3, 4}; -//// tables = {Table(1, 0), Table(1, 1), Table(1, 2), Table(1, 3), Table(1, 4)}; -//// -//// merge(2, 4); -//// ASSERT_EQ(2, maximumNumberOfRows); -//// -//// merge(1, 3); -//// ASSERT_EQ(2, maximumNumberOfRows); -//// -//// merge(0, 3); -//// ASSERT_EQ(3, maximumNumberOfRows); -//// -//// merge(4, 3); -//// ASSERT_EQ(5, maximumNumberOfRows); -//// -//// merge(4, 2); -//// ASSERT_EQ(5, maximumNumberOfRows); -////} -//// -////TEST(MergingTables, t1) { -//// maximumNumberOfRows = 10; -//// rank = {0, 0, 0, 0, 0, 0}; -//// parent = {0, 1, 2, 3, 4, 5}; -//// tables = {Table(10, 0), Table(0, 1), Table(5, 2), Table(0, 3), Table(3, 4), Table(3, 5)}; -//// -//// merge(5, 5); -//// ASSERT_EQ(10, maximumNumberOfRows); -//// -//// merge(5, 4); -//// ASSERT_EQ(10, maximumNumberOfRows); -//// -//// merge(4, 3); -//// ASSERT_EQ(10, maximumNumberOfRows); -//// -//// merge(3, 2); -//// ASSERT_EQ(11, maximumNumberOfRows); -////} |