fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <utility>
  7. #include <algorithm>
  8. #include <string>
  9.  
  10. using namespace std;
  11.  
  12. #define ll long long
  13.  
  14. vector<string> list_string[25];
  15. vector<ll> hash_list[25][2];
  16.  
  17. bool skip[20000];
  18. int main() {
  19.  
  20.     // std::ios::sync_with_stdio(false);
  21.     int tc;
  22.     cin >> tc;
  23.     for(int kasus = 1; kasus<=tc; kasus++) {
  24.  
  25.         printf("Case #%d: ",kasus);
  26.  
  27.         int n;
  28.         cin >> n;
  29.         for(int i=1; i<=20; i++) {
  30.             list_string[i].clear();
  31.             for(int j =0 ; j<2; j++) {
  32.                 hash_list[i][j].clear();
  33.             }
  34.         }
  35.         int st =0 ;
  36.         for(int i = 0; i< n; i++) {
  37.             string temp;
  38.             cin >> temp;
  39.             int pjg = temp.length();
  40.             st = max(st,pjg);
  41.             list_string[pjg].push_back(temp);
  42.             ll hash =0, hash2 ;
  43.             for(int j =0 ; j < (int) temp.length()-1; j++) {
  44.                 hash*= 31;
  45.                 hash+= (temp[j]-'A'+1);
  46.             }
  47.             hash_list[pjg][0].push_back(hash);
  48.             hash2=hash*31;
  49.             hash2+=temp[pjg-1]-'A'+1;
  50.             hash_list[pjg][1].push_back(hash2);
  51.             //cout << temp << '=' << hash << ',' << hash2 << '\n';
  52.         }
  53.         int v =0;
  54.         map<ll, int> last;
  55.         for(int pjg = st; pjg > 0; pjg--) {
  56.             vector<string> &lx = list_string[pjg];
  57.             //cout << "PANJANG " << pjg << '\n';
  58.             for(int i =0 ; i < (int)lx.size(); i++) {
  59.                 skip[i] = false;
  60.                 ll hash_full = hash_list[pjg][1][i];
  61.                 if(last[hash_full]>0) {
  62.                     v++;
  63.                     last[hash_full]--;
  64.                     skip[i] = true;
  65.                 } else {
  66.                     //cout << "TIDAK ADA " << hash_full << '\n';
  67.                 }
  68.             }
  69.             last.clear();
  70.             for(int i =0 ; i < (int)lx.size(); i++) {
  71.                 if(skip[i]) {
  72.                     continue;
  73.                 }
  74.                 ll hash_gk_full = hash_list[pjg][0][i];
  75.                 last[hash_gk_full]++;
  76.                 // cout << "MASUKKAN " << lx[i] << ' ' << hash_gk_full << '\n';
  77.             }
  78.         }
  79.  
  80.         printf("%d\n",v);
  81.  
  82.     }
  83. }
  84.  
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
1
4
ABC
AB
A
AC
stdout
copy 
Case #1: 2
https://ideone.com/PGjPAq
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!