Advertisement
Guest User

Untitled

a guest
Mar 24th, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i,a,b) for(int i = (a); i < (b); ++i)
  5. #define RFOR(i,b,a) for(int i = (b)-1; i >= (a); --i)
  6. #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
  7. #define FILL(a,value) memset(a, value, sizeof(a))
  8.  
  9. #define SZ(a) (LL)a.size()
  10. #define ALL(a) a.begin(), a.end()
  11. #define PB push_back
  12. #define MP make_pair
  13.  
  14. typedef long long LL;
  15. typedef vector<int> VI;
  16. typedef pair<int, int> PII;
  17.  
  18. const double PI = acos(-1.0);
  19. const int INF = 1000 * 1000 * 1000 + 7;
  20. const LL LINF = INF * (LL)INF;
  21.  
  22. map<string, vector<string> > files;
  23. map<string, vector<string> > users;
  24.  
  25. int count(string& a, string& b)
  26. {
  27.     int res = 0;
  28.     int ind = 0;
  29.     FOR (i, 0, SZ(b))
  30.     {
  31.         while(ind < SZ(a) && a[ind] != b[i])
  32.         {
  33.             ind++;
  34.             res++;
  35.         }
  36.  
  37.         if (res > 2) return INF;
  38.  
  39.         if (ind == SZ(a)) return INF;
  40.         ind++;
  41.     }
  42.  
  43.     while(ind < SZ(a))
  44.     {
  45.         ind++;
  46.         res++;
  47.     }
  48.  
  49.     return res;
  50. }
  51.  
  52. int main()
  53. {
  54.     //freopen("in.txt", "r", stdin);
  55.     //ios::sync_with_stdio(false); cin.tie(0);
  56.  
  57.     int tt;
  58.     cin>>tt;
  59.     FOR (ttt, 0, tt)
  60.     {
  61.         files.clear();
  62.         users.clear();
  63.  
  64.         int n;
  65.         cin>>n;
  66.         FOR (i, 0, n)
  67.         {
  68.             string dir, file;
  69.             cin>>dir>>file;
  70.  
  71.             files[dir].PB(file);
  72.         }
  73.  
  74.         cin>>n;
  75.         FOR (i, 0, n)
  76.         {
  77.             string name;
  78.             cin>>name;
  79.             int k;
  80.             cin>>k;
  81.             FOR (i, 0, k)
  82.             {
  83.                 string dir;
  84.                 cin>>dir;
  85.                 users[name].PB(dir);
  86.             }
  87.         }
  88.  
  89.         printf("DATA SET #%d\n", ttt + 1);
  90.  
  91.         cin >> n;
  92.         FOR (i, 0, n)
  93.         {
  94.             string name, file;
  95.             cin>>name>>file;
  96.  
  97.             vector<string>& dirs = users[name];
  98.  
  99.             vector<pair<string, string> > res;
  100.  
  101.             FOR (it, 0, 3)
  102.             {
  103.                 FOR (j, 0, SZ(dirs))
  104.                 {
  105.                     vector<string>& fs = files[dirs[j]];
  106.  
  107.                     FOR (k, 0, SZ(fs))
  108.                     {
  109.                         if (count(fs[k], file) == it) res.PB(MP(fs[k], dirs[j]));
  110.                     }
  111.  
  112.                     if (SZ(res)) break;
  113.                 }
  114.                 if (SZ(res)) break;
  115.             }
  116.  
  117.             sort(ALL(res));
  118.  
  119.             printf("%s REQUESTED %s\n", name.c_str(), file.c_str());
  120.             FOR (i, 0, SZ(res))
  121.             {
  122.                 printf("FOUND %s IN %s\n", res[i].first.c_str(), res[i].second.c_str());
  123.             }
  124.         }
  125.     }
  126.  
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement