knakul853

Untitled

Oct 31st, 2020
1,089
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/tree_policy.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/rope>
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. using namespace __gnu_cxx;
  8.  
  9. #define mod 1000000007
  10.  /*
  11.     /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ *** Debugging Start *** \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
  12. */
  13. void __print(int x) {cerr << x;}
  14. void __print(long x) {cerr << x;}
  15. void __print(long long x) {cerr << x;}
  16. void __print(unsigned x) {cerr << x;}
  17. void __print(unsigned long x) {cerr << x;}
  18. void __print(unsigned long long x) {cerr << x;}
  19. void __print(float x) {cerr << x;}
  20. void __print(double x) {cerr << x;}
  21. void __print(long double x) {cerr << x;}
  22. void __print(char x) {cerr << '\'' << x << '\'';}
  23. void __print(const char *x) {cerr << '\"' << x << '\"';}
  24. void __print(const string &x) {cerr << '\"' << x << '\"';}
  25. void __print(bool x) {cerr << (x ? "true" : "false");}    
  26. template<typename T, typename V>
  27. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  28. template<typename T>
  29. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  30. void _print() {cerr << "]\n";}
  31. template <typename T, typename... V>
  32. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  33. #ifndef ONLINE_JUDGE
  34. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  35. #else
  36. #define debug(x...)
  37. #endif
  38. /*
  39.     /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ *** Debugging Ends *** \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
  40. */
  41. using namespace __gnu_pbds;
  42. template <typename T>
  43. using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  44.      
  45. /// Some frequent usable functions
  46. #define int                        long long
  47. void add(int &a,int b){a+=b;if(a>mod)a-=mod;}
  48. void sub(int &a,int b){a-=b;if(a<0)a+=mod;}
  49. void mul(int &a, int b) {a=1ll * a * b % mod;}
  50. template<typename T> T pow(T a,T b, long long m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }
  51. int powmod(int a,int b)
  52. {int res = 1;while(b){if(b&1){res = (res * a)%mod;}b= b/2;a = (a*a)%mod;}return res;}
  53. int _ceil(int, int);
  54. int _floor(int a, int b) { return b < 0 ? _floor(-a, -b) : a < 0 ? -_ceil(-a, b) : a / b; }
  55. int _ceil(int a, int b) { return b < 0 ? _ceil(-a, -b) : a < 0 ? -_floor(-a, b) : (a + b - 1) / b; }
  56.      
  57. // int gcd(int a, int b, int &x, int &y) {if (a == 0) {x = 0; y = 1;return b;
  58. //     }int x1, y1;int d = gcd(b%a, a, x1, y1); x = y1 - (b / a) * x1;y = x1;return d;}
  59. // int find(int v){return v==parent[v]?v:parent[v] = find(parent[v]);}
  60. // void merge(int i,int j)
  61. //     {i = find(i);j = find(j);if(i == j)return;parent[parent[i]] = parent[j];cmp--;}
  62.      
  63. /*
  64.     /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ *** Directions in grids *** \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
  65. */
  66. // int dy[4] = {0,0,1,-1}, dx[4] = {1,-1,0,0}; // 4 Direction
  67. // int dx[] = {1,-1,0,0,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1,1,-1};  // 8 Direction
  68. // int dx[] = {1,-1,1,-1,2,2,-2,-2} , dy[] = {2,2,-2,-2,1,-1,1,-1};  // Knight moves
  69. // int dx[] = {2,-2,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1};  // Hexagonal Direction
  70. #pragma GCC target ("avx2")
  71. #pragma GCC optimization ("O3")
  72. #pragma GCC optimization ("unroll-loops")
  73. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  74. #define sp(a , x) cout << fixed << setprecision(a) << x << endl;
  75. #define endl "\n"
  76. #define pb push_back
  77. #define pf push_front
  78. #define ub upper_bound
  79. #define lb lower_bound
  80. #define F first
  81. #define S second
  82. #define mset(a, b) memset(a, b, sizeof a)
  83. #define sz(x) ((int)(x.size()))
  84. #define sqr(x) ((x) * (x))
  85. #define graph vector<int>
  86. #define vi vector<int>
  87. #define vvi vector<vector<int>>
  88. #define pi pair<int,int>
  89. #define all(c)                      c.begin() , c.end()
  90. #define rep(i,a) for(int i=0;i<a;i++)
  91. #define rrep(i,a,b) for(int i=a;i>=b;i--)
  92. #define iter(it,a) for(auto it=a.begin();it!=a.end();it++)
  93. #define PQP priority_queue<pi, vector<pi>, greater<pi>>
  94. #define PQI priority_queue<int, vector<int>, greater<int>>
  95. #define dbg debug
  96. #define inf (int)1e18
  97. const long double EPS = 0.0000000001;
  98. const long double PI = 3.1415926535897932384;
  99. //vec.resize(unique(all(vec)) - vec.begin());
  100.  int dy[4] = {0,0,1,-1}, dx[4] = {1,-1,0,0};
  101.  
  102.  // Template Ends Here.
  103.      
  104.   /// define some data....... |
  105. const int N = (int)50;
  106. int n;
  107.  
  108. int HASH1( string s){
  109.  
  110.     int sum = 0;
  111.     for (int i = 0; i < s.size(); i++){
  112.         sum += s[i];
  113.     }
  114.     return sum % n;
  115. }
  116.  
  117. int HASH2( string s){
  118.  
  119.     int sum = 0;
  120.     for (int i = 0; i < s.size(); i++){
  121.         sum += s[i]%13;
  122.     }
  123.     return sum % n;
  124. }
  125.  
  126. void solve()
  127. {
  128.     cin >> n;
  129.  
  130.     vector<int> bloom_filter(n, 0);
  131.  
  132.     int m;
  133.     cin >> m;
  134.     for (int i = 0; i < m; i++){
  135.         string s;
  136.         cin >> s;
  137.         int hash1 = HASH1(s);
  138.         int hash2 = HASH2(s);
  139.  
  140.         bloom_filter[hash2] = bloom_filter[hash1] = 1;
  141.     }
  142.  
  143.     int q;
  144.     cin >> q;
  145.     for (int i = 0; i < q; i++)
  146.     {
  147.         string s;
  148.         cin >> s;
  149.         int hash1 = HASH1(s);
  150.         int hash2 = HASH2(s);
  151.  
  152.         /*
  153.         1. Bloom filters never generate false negative result, i.e.,
  154.            telling you that a username doesn’t exist when it actually exists.
  155.  
  156.         2. False positive means, it might tell that given username is
  157.            already taken but actually it’s not.
  158.         */
  159.         if(bloom_filter[hash1] && bloom_filter[hash2]){
  160.             cout << "Definitely not\n";
  161.         }
  162.         else{
  163.             cout <<"May be\n";
  164.         }  
  165.     }
  166. }
  167.  
  168. int32_t main(){
  169.     fast;
  170.     int test = 1;
  171.     // cin >> test;
  172.     int tc = 1;
  173.     while (test--)
  174.     {
  175.         solve();
  176.     }
  177. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×