fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define TABLE_SIZE 101
  3.  
  4. using namespace std;
  5.  
  6. static int cnt = 0;
  7. vector<string> HashTable(TABLE_SIZE,"");
  8.  
  9. int h (string key){
  10.     long long int sum = 0;
  11.     for(int i =0; i<key.size(); i++){
  12.         sum += key[i]*(i+1);
  13.     }
  14.     return 19*sum;
  15. }
  16.  
  17. int Hash(string key){
  18.     long long int sum = h(key);
  19.     return sum%101;
  20. }
  21.  
  22. void hash_insert(string key){
  23.     int hash_slot = Hash(key);
  24.     int j=1;
  25.  
  26.     if(find(HashTable.begin(), HashTable.end(), key)!=HashTable.end()){
  27.         return;
  28.     }
  29.  
  30.     while ( HashTable[hash_slot] != "" && j < 20){
  31.         hash_slot = int((Hash(key) + pow(j,2) + 23*j))%101;
  32.         //cout<<hash_slot<<"\n";
  33.         j++;
  34.     }
  35.     HashTable[hash_slot] = key;
  36.     cnt += 1;
  37. }
  38.  
  39. void hash_delete(string key){
  40.     if(find(HashTable.begin(), HashTable.end(), key)== HashTable.end()){
  41.         return;
  42.     }
  43.     int hash_slot = Hash(key);
  44.     while ( HashTable[hash_slot] != key){
  45.         hash_slot = (hash_slot+1)%101;
  46.     }
  47.     HashTable[hash_slot] = "";
  48.     cnt -= 1;
  49. }
  50.  
  51. int main(){
  52.     int i;
  53.  
  54.     cin>>i;
  55.     while(i--){
  56.         int j;
  57.         cin>>j;
  58.         while(j--){
  59.             string key, initial="";
  60.             int ind=0;
  61.             cin>>key;
  62.             while(ind!=3){
  63.                 initial += key[ind++];
  64.             }
  65.  
  66.             key.erase(0,4);
  67.  
  68.             if(initial == "ADD"){
  69.                 hash_insert(key);
  70.             }
  71.             else{
  72.                 hash_delete(key);
  73.             }
  74.         }
  75.  
  76.         cout<<cnt<<"\n";
  77.         for(int i=0; i<TABLE_SIZE;i++){
  78.             if(HashTable[i]!=""){
  79.                 cout<<i<<":"<<HashTable[i]<<"\n";
  80.             }
  81.         }
  82.         fill(HashTable.begin(), HashTable.end(), "");
  83.         cnt = 0;
  84.     }
  85. }
  86.  
Success #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
2
1
ADD:Spoj
2
ADD:Love
DEL:Love
stdout
copy 
1
16:Spoj
0
https://ideone.com/iGsnkq
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!