Phone book done!

1 files changed, 163 insertions, 108 deletions

diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 2c444df..07f8b43 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,135 +1,190 @@
-#include <cstdio>
-#include <cstdlib>
-#include <vector>
-#include <algorithm>
 #include <iostream>
-//#include <gtest/gtest.h>
+#include <vector>
+#include <string>
 
-using std::cin;
-using std::cout;
-using std::endl;
-using std::max;
+using std::string;
 using std::vector;
+using std::cin;
 
-struct Table {
-	int numberOfRows;
-	int setID;
-
-	Table(int numberOfRows, int setID) :
-			numberOfRows(numberOfRows), setID(setID) {
-	}
+struct Query {
+    string type, name;
+    int number;
 };
 
-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];
+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;
 }
 
-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 write_responses(const vector<string>& result) {
+    for (size_t i = 0; i < result.size(); ++i)
+        std::cout << result[i] << "\n";
 }
 
-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);
+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;
 }
 
 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;
+    write_responses(process_queries(read_queries()));
+    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)};
+//#include <cstdio>
+//#include <cstdlib>
+//#include <vector>
+//#include <algorithm>
+//#include <iostream>
+////#include <gtest/gtest.h>
 //
-//    merge(2, 4);
-//    ASSERT_EQ(2, maximumNumberOfRows);
+//using std::cin;
+//using std::cout;
+//using std::endl;
+//using std::max;
+//using std::vector;
 //
-//    merge(1, 3);
-//    ASSERT_EQ(2, maximumNumberOfRows);
+//struct Table {
+//	int numberOfRows;
+//	int setID;
 //
-//    merge(0, 3);
-//    ASSERT_EQ(3, maximumNumberOfRows);
+//	Table(int numberOfRows, int setID) :
+//			numberOfRows(numberOfRows), setID(setID) {
+//	}
+//};
 //
-//    merge(4, 3);
-//    ASSERT_EQ(5, maximumNumberOfRows);
+//int maximumNumberOfRows = -1;
+//vector<int> parent;
+//vector<int> rank;
+//vector<Table> tables;
 //
-//    merge(4, 2);
-//    ASSERT_EQ(5, maximumNumberOfRows);
+//int find(int i) {
+//	if (i != parent[i])
+//		parent[i] = find(parent[i]);
+//	return parent[i];
 //}
 //
-//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)};
+//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;
+//	}
+//}
 //
-//    merge(5, 5);
-//    ASSERT_EQ(10, maximumNumberOfRows);
+//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);
+//}
 //
-//    merge(5, 4);
-//    ASSERT_EQ(10, maximumNumberOfRows);
+//int main() {
+//	int n, m;
+//	cin >> n >> m;
 //
-//    merge(4, 3);
-//    ASSERT_EQ(10, maximumNumberOfRows);
+//	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);
+//	}
 //
-//    merge(3, 2);
-//    ASSERT_EQ(11, maximumNumberOfRows);
+//	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);
+////}