Advertisement
Guest User

Untitled

a guest
Nov 18th, 2017
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <unordered_set>
  3. using namespace std;
  4.  
  5. #define st first
  6. #define nd second
  7. #define pb push_back
  8. #define mp make_pair
  9. #define klar(v) memset(v, 0, sizeof(v))
  10. #define bust ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  11. #define gcd(a, b) __gcd(a, b);
  12. #define debug cout << "chuj" << endl;
  13. #define endl "\n"
  14.  
  15. typedef vector<int> vi;
  16. typedef vector<pair<int, int> > vpii;
  17. typedef vector<long long> vll;
  18. typedef pair<int, int> pii;
  19. typedef pair<long long, long long> pll;
  20. typedef long long ll;
  21. const int mod = 1e8+37, mod2 = 1e9+7, prime = 137, maxn = 1e5+100;
  22.  
  23. vi arr[maxn];
  24. int primes[maxn], primes2[maxn];
  25. set <pii> keks[maxn];
  26. pii gethasz(int n, int h, int it, ll hasz){
  27.     int w = n-it;
  28.     ll hasz2 = (1LL*mod+hasz-(1LL*arr[h][it]*primes[w])%mod)%mod;
  29.     hasz = (1LL*mod2+hasz-(1LL*arr[h][it]*primes[w])%mod2)%mod2;
  30.     return mp(hasz2, hasz);
  31. }
  32.  
  33. int main(){
  34.     primes[0] = 1;
  35.     for(int i = 1; i < maxn; i++)
  36.         primes[i] = (1LL*primes[i-1]*prime)%mod;
  37.     int n, m;
  38.     scanf("%d%d", &n, &m);
  39.     for(int i = 1; i <= n; i++){
  40.         int xn;
  41.         scanf("%d", &xn);
  42.         arr[i].reserve(xn+5);
  43.         arr[i].pb(0);
  44.         for(int j = 1; j <= xn; j++){
  45.             int x;
  46.             scanf("%d", &x);
  47.             arr[i].pb(x);
  48. //            arr[i][j]++;
  49.         }
  50.         ll ahasz = 0;
  51.         for(int j = 1; j <= xn; j++)
  52.             ahasz = (ahasz*prime+arr[i][j])%mod;
  53.         for(int j = 1; j <= xn; j++)
  54.             keks[xn-1].insert(gethasz(xn, i, j, ahasz));
  55.     }
  56.     while(m--){
  57.         int xn;
  58.         scanf("%d", &xn);
  59.         vi ac;
  60.         ac.reserve(xn+3);
  61.         ll allhasz = 0;
  62.         ac.pb(0);
  63.         for(int i = 1; i <= xn; i++){
  64.             int x;
  65.             scanf("%d", &x);
  66.             ac.pb(x);
  67. //            ac[i]++;
  68.             allhasz = (allhasz*prime+ac[i])%mod;
  69.         }
  70.         bool ans = 0;
  71.         for(int i = 1; i <= xn; i++){
  72.             int h = xn-i;
  73.             int szuk1 = (mod+allhasz-(1LL*ac[i]*primes[h])%mod)%mod;
  74.             int szuk2 = (mod2+allhasz-(1LL*ac[i]*primes[h])%mod2)%mod2;
  75.             if(keks[xn-1].find(mp(szuk1, szuk2)) != keks[xn-1].end())ans = 1;
  76.         }
  77.         if(ans)printf("TAK\n");
  78.         else printf("NIE\n");
  79.     }
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement