daily pastebin goal
58%
SHARE
TWEET

Untitled

a guest Mar 24th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <unordered_set>
  5. #include <random>
  6. #include <ctime>
  7.  
  8. using namespace std;
  9. #define ll unsigned long long
  10.  
  11. ll p = 1111111111111111111ll;
  12. uint32_t sz = 100;
  13. vector<list<pair<string, unordered_set<string>>>> vec
  14.         = vector<list<pair<string, unordered_set<string>>>>(sz);
  15. ll numberOfElements = 0;
  16.  
  17.  
  18. ll myRand() {
  19.     mt19937 gen(static_cast<unsigned int>(time(nullptr)));
  20.     return (ll) uniform_int_distribution<unsigned int>(1, static_cast<unsigned int>(1e9))(gen);
  21. }
  22.  
  23.  
  24. ll a = myRand();
  25.  
  26. uint32_t myHashX(string x) {
  27.     ll hash = 0;
  28.     for (char i : x) {
  29.         hash *= a;
  30.         hash += i;
  31.         hash %= p;
  32.     }
  33.     hash %= sz;
  34.     return (uint32_t) hash;
  35. }
  36.  
  37. void rehash() {
  38.     sz *= 2;
  39.     vector<list<pair<string, unordered_set<string>>>> vec2;
  40.     vec2.resize(sz);
  41.     for (auto i : vec) {
  42.         for (auto k : i) {
  43.             uint32_t hashX = myHashX(k.first);
  44.             pair<string, unordered_set<string>> p;
  45.             p.first = k.first;
  46.             for (const auto &j : k.second) {
  47.                 p.second.insert(j);
  48.             }
  49.             vec2[hashX].push_front(p);
  50.         }
  51.     }
  52.     vec = vec2;
  53. }
  54.  
  55.  
  56. vector<string> ans = vector<string>(500);
  57.  
  58. int get(const string &x, uint32_t hashX) {
  59.     uint32_t cnt = 0;
  60.     for (auto &it : vec[hashX]) {
  61.         if (it.first == x) {
  62.             for (const auto &t : it.second) {
  63.                 ans[cnt++] = t;
  64.             }
  65.         }
  66.     }
  67.     return cnt;
  68. }
  69.  
  70. void insert(const string &x, uint32_t hashX, const string &y) {
  71.     for (auto &it : vec[hashX]) {
  72.         if (it.first == x) {
  73.             it.second.insert(y);
  74.             return;
  75.         }
  76.     }
  77.     pair<string, unordered_set<string>> p;
  78.     p.first = x;
  79.     p.second.insert(y);
  80.     vec[hashX].push_front(p);
  81.     numberOfElements++;
  82.     if (numberOfElements > sz) {
  83.         rehash();
  84.     }
  85. }
  86.  
  87. void erase(const string &x, uint32_t hashX, const string &y) {
  88.     for (auto &it : vec[hashX]) {
  89.         if (it.first == x) {
  90.             for (const auto &t : it.second) {
  91.                 if (t == y) {
  92.                     it.second.erase(t);
  93.                     return;
  94.                 }
  95.             }
  96.         }
  97.     }
  98. }
  99.  
  100. void deleteAll(const string &x, uint32_t hashX) {
  101.     for (auto it = vec[hashX].begin(); it != vec[hashX].end(); it++) {
  102.         if ((*it).first == x) {
  103.             vec[hashX].erase(it);
  104.             numberOfElements--;
  105.             return;
  106.         }
  107.     }
  108. }
  109.  
  110. int main() {
  111.     ios::sync_with_stdio(false);
  112.     cin.tie(nullptr);
  113.     cout.tie(nullptr);
  114.     freopen("multimap.in", "r", stdin);
  115.     freopen("multimap.out", "w", stdout);
  116.     string s;
  117.     string x, y;
  118.     while (cin >> s) {
  119.         cin >> x;
  120.         uint32_t hashX = myHashX(x);
  121.         if (s[0] == 'p') {
  122.             cin >> y;
  123.             insert(x, hashX, y);
  124.         } else if (s[0] == 'g') {
  125.             auto t = get(x, hashX);
  126.             cout << t << " ";
  127.             for (uint32_t i = 0; i < (uint32_t) t; i++) {
  128.                 cout << ans[i] << " ";
  129.             }
  130.             cout << '\n';
  131.         } else if (s == "delete") {
  132.             cin >> y;
  133.             erase(x, hashX, y);
  134.         } else {
  135.             deleteAll(x, hashX);
  136.         }
  137.     }
  138.     return 0;
  139. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top