Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2019
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.63 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:25600000")
  2. #define _CRT_NO_WARNINGS
  3. #include <iostream>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <cmath>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <algorithm>
  11. #include <cstring>
  12. #include <map>
  13. #include <queue>
  14. #include <set>
  15. #include <cassert>
  16. #include <complex>
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef vector<int> VI;
  22. typedef vector< vector<int> > VVI;
  23. typedef pair<int, int> PII;
  24. typedef vector<PII> VPII;
  25.  
  26. #define REP(i, n) for(int i = 0; i < n; ++i)
  27. #define RREP(i, n) for(int i = n - 1; i >= 0; --i)
  28. #define FOR(i, x, y) for(int i = x; i <= y; ++i)
  29. #define RFOR(i, x, y) for(int i = x; i >= y; --i)
  30. #define SZ(a) (int)(a).size()
  31. #define ALL(a) (a).begin(),(a).end()
  32. #define SORT(a) sort(ALL(a))
  33. #define CLEAR(x) memset(x,0,sizeof x);
  34. #define UNIQUE(c) SORT(c),(c).resize(unique(ALL(c))-(c).begin())
  35. #define pb push_back
  36. #define sqr(x) (x)*(x)
  37.  
  38. const double pi=acos(-1.0);
  39. const double eps = 1e-9;
  40. const int MAXN = 510000;
  41.  
  42. set<int> bad;
  43. int n, N1, N2, NP, hs;
  44. char s[MAXN];
  45. int seq[MAXN];
  46. int a[MAXN];
  47. PII pairs[MAXN];
  48.  
  49. int main()
  50. {
  51.     scanf("%d\n", &n);
  52.     REP(i, n)
  53.     {
  54.         gets(s);
  55.         REP(i, strlen(s))
  56.         {
  57.             if (s[i] >= 'A' && s[i] <= 'Z')
  58.                 s[i] = s[i] - 'A' + 'a';
  59.         }
  60.  
  61.         REP(i, strlen(s))
  62.         if (isalpha(s[i]))
  63.         {
  64.             hs = 0;        
  65.             while(true)
  66.             {
  67.                 hs = hs * 30 + s[i] - 'a';
  68.                 ++i;
  69.                 if (i >= strlen(s) || !isalpha(s[i])) break;
  70.             }          
  71.             seq[N1++] = hs;
  72.         }
  73.     }
  74.  
  75.     scanf("%d\n", &n);
  76.     REP(i, n)
  77.     {
  78.         gets(s);
  79.         hs = 0;
  80.         REP(i, strlen(s))
  81.             hs = hs * 30 + s[i] - 'a';
  82.         bad.insert(hs);    
  83.     }
  84.  
  85.     REP(i, N1)
  86.         if (bad.find(seq[i]) == bad.end())
  87.         {
  88.             a[N2++] = seq[i];
  89.         }
  90.  
  91.     NP = N2 - 1;
  92.     REP(i, NP)
  93.     {
  94.         int t1 = a[i];
  95.         int t2 = a[i + 1];
  96.         if (t1 > t2) swap(t1, t2);
  97.         pairs[i] = PII(t1, t2);
  98.     }
  99.  
  100.     sort(a, a + N2);
  101.     sort(pairs, pairs + NP);
  102.  
  103.     int q;
  104.     scanf("%d\n", &q);
  105.     REP(query, q)
  106.     {
  107.         gets(s);       
  108.         bool f = false;
  109.         int h1 = 0;
  110.         int h2 = 0;
  111.         REP(i, strlen(s))
  112.         {
  113.             if (isalpha(s[i]))
  114.             {
  115.                 if (!f) h1 = h1 * 30 + s[i] - 'a';
  116.                 if (f) h2 = h2 * 30 + s[i] - 'a';
  117.             }
  118.             else
  119.             {
  120.                 f = true;
  121.             }
  122.         }
  123.        
  124.         if (h1 > h2) swap(h1, h2);
  125.         PII t = make_pair(h1, h2);
  126.         double p0 = upper_bound(pairs, pairs + NP, t) - lower_bound(pairs, pairs + NP, t); p0 /= NP;
  127.         double res = 0;
  128.  
  129.         if (p0 > 0.0)
  130.         {          
  131.             double p1 = upper_bound(a, a + N2, h1) - lower_bound(a, a + N2, h1); p1 /= N2;
  132.             double p2 = upper_bound(a, a + N2, h2) - lower_bound(a, a + N2, h2); p1 /= N2;
  133.             res = p0 / p1 / p2;
  134.         }
  135.         printf("%.7lf\n", res);    
  136.     }
  137. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement