Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- std::string str = "none";
- const int N = 100000;
- const std::string aaa = "aaaaaaaaaaaaaaaaaaaaa";
- std::string prev1 = aaa;
- struct hashset {
- std::vector<std::string> a[N];
- int get_hash(std::string x) {
- int t = 0;
- for (int i = 0; i < x.length(); i++)
- t += ((i + 1)*int(x[i]));
- return t;
- }
- void add_next(std::string next2, std::string x) {
- int hash = get_hash(x);
- std::string y, prev2;
- for (long long i = 0; i < a[hash].size(); i += 4) {
- if (x == a[hash][i]) {
- y = a[hash][i + 1];
- prev2 = a[hash][i + 2];
- std::swap(a[hash][i], a[hash][a[hash].size() - 4]);
- std::swap(a[hash][i + 1], a[hash][a[hash].size() - 3]);
- std::swap(a[hash][i + 2], a[hash][a[hash].size() - 2]);
- std::swap(a[hash][i + 3], a[hash][a[hash].size() - 1]);
- a[hash].pop_back();
- a[hash].pop_back();
- a[hash].pop_back();
- a[hash].pop_back();
- }
- }
- a[hash].push_back(x);
- a[hash].push_back(y);
- a[hash].push_back(prev2);
- a[hash].push_back(next2);
- }
- void add_prev(std::string prev2, std::string x) {
- int hash = get_hash(x);
- std::string y, next2;
- for (long long i = 0; i < a[hash].size(); i += 4) {
- if (x == a[hash][i]) {
- y = a[hash][i + 1];
- next2 = a[hash][i + 3];
- std::swap(a[hash][i], a[hash][a[hash].size() - 4]);
- std::swap(a[hash][i + 1], a[hash][a[hash].size() - 3]);
- std::swap(a[hash][i + 2], a[hash][a[hash].size() - 2]);
- std::swap(a[hash][i + 3], a[hash][a[hash].size() - 1]);
- a[hash].pop_back();
- a[hash].pop_back();
- a[hash].pop_back();
- a[hash].pop_back();
- }
- }
- a[hash].push_back(x);
- a[hash].push_back(y);
- a[hash].push_back(prev2);
- a[hash].push_back(next2);
- }
- void put(std::string x, std::string y) {
- int hash = get_hash(x);
- std::string tmp1 = prev1;
- std::string tmp2 = aaa;
- int tmp3 = 0;
- for (long long i = 0; i < a[hash].size(); i+=4) {
- if (x == a[hash][i]) {
- tmp1 = a[hash][i + 2];
- tmp2 = a[hash][i + 3];
- tmp3 = 1;
- std::swap(a[hash][i], a[hash][a[hash].size() - 4]);
- std::swap(a[hash][i + 1], a[hash][a[hash].size() - 3]);
- std::swap(a[hash][i + 2], a[hash][a[hash].size() - 2]);
- std::swap(a[hash][i + 3], a[hash][a[hash].size() - 1]);
- a[hash].pop_back();
- a[hash].pop_back();
- a[hash].pop_back();
- a[hash].pop_back();
- }
- }
- a[hash].push_back(x);
- a[hash].push_back(y);
- a[hash].push_back(tmp1);
- a[hash].push_back(tmp2);
- if (tmp3 != 1) {
- if (x != prev1 && prev1 != aaa) add_next(x, prev1);
- prev1 = x;
- }
- }
- void del(std::string x) {
- int hash = get_hash(x);
- for (long long i = 0; i < a[hash].size(); i+=4) {
- if (x == a[hash][i]) {
- if (a[hash][i + 3] == a[hash][i + 2] && a[hash][i + 3] == aaa) prev1 = a[hash][i + 2];
- add_next(a[hash][i + 3], a[hash][i + 2]);
- if (a[hash][i + 3] != aaa) add_prev(a[hash][i + 2], a[hash][i + 3]);
- prev1 = a[hash][i + 2];
- std::swap(a[hash][i], a[hash][a[hash].size() - 4]);
- std::swap(a[hash][i + 1], a[hash][a[hash].size() - 3]);
- std::swap(a[hash][i + 2], a[hash][a[hash].size() - 2]);
- std::swap(a[hash][i + 3], a[hash][a[hash].size() - 1]);
- a[hash].pop_back();
- a[hash].pop_back();
- a[hash].pop_back();
- a[hash].pop_back();
- return;
- }
- }
- }
- std::string get(std::string x) {
- int hash = get_hash(x);
- for (long long i = 0; i < a[hash].size(); i+=4) {
- if (x == a[hash][i] && a[hash][i + 1] != "") return a[hash][i + 1];
- }
- return str;
- }
- std::string next(std::string x) {
- int hash = get_hash(x);
- for (long long i = 0; i < a[hash].size(); i+=4) {
- if (x == a[hash][i] && a[hash][i + 3] != aaa) return get(a[hash][i + 3]);
- }
- return str;
- }
- std::string prev(std::string x) {
- int hash = get_hash(x);
- for (long long i = 0; i < a[hash].size(); i+=4) {
- if (x == a[hash][i] && a[hash][i + 2] != aaa) return get(a[hash][i + 2]);
- }
- return str;
- }
- };
- int main() {
- std::ios_base::sync_with_stdio(false);
- freopen("linkedmap.in", "r", stdin);
- freopen("linkedmap.out", "w", stdout);
- hashset map = *new hashset();
- std::string text;
- std::string x, y;
- while (std::cin >> text)
- {
- if (text == "put") {
- std::cin >> x >> y;
- map.put(x, y);
- } else if (text == "get") {
- std::cin >> x;
- std::cout << map.get(x) << "\n";
- } else if (text == "next") {
- std::cin >> x;
- std::cout << map.next(x) << "\n";
- } else if (text == "prev") {
- std::cin >> x;
- std::cout << map.prev(x) << "\n";
- } else {
- std::cin >> x;
- map.del(x);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement