Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <unordered_set>
- using namespace std;
- #define st first
- #define nd second
- #define pb push_back
- #define mp make_pair
- #define klar(v) memset(v, 0, sizeof(v))
- #define bust ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- #define gcd(a, b) __gcd(a, b);
- #define debug cout << "chuj" << endl;
- #define endl "\n"
- typedef vector<int> vi;
- typedef vector<pair<int, int> > vpii;
- typedef vector<long long> vll;
- typedef pair<int, int> pii;
- typedef pair<long long, long long> pll;
- typedef long long ll;
- const int mod = 1e8+37, mod2 = 1e9+7, prime = 137, maxn = 1e5+100;
- vi arr[maxn];
- int primes[maxn], primes2[maxn];
- set <pii> keks[maxn];
- pii gethasz(int n, int h, int it, ll hasz){
- int w = n-it;
- ll hasz2 = (1LL*mod+hasz-(1LL*arr[h][it]*primes[w])%mod)%mod;
- hasz = (1LL*mod2+hasz-(1LL*arr[h][it]*primes[w])%mod2)%mod2;
- return mp(hasz2, hasz);
- }
- int main(){
- primes[0] = 1;
- for(int i = 1; i < maxn; i++)
- primes[i] = (1LL*primes[i-1]*prime)%mod;
- int n, m;
- scanf("%d%d", &n, &m);
- for(int i = 1; i <= n; i++){
- int xn;
- scanf("%d", &xn);
- arr[i].reserve(xn+5);
- arr[i].pb(0);
- for(int j = 1; j <= xn; j++){
- int x;
- scanf("%d", &x);
- arr[i].pb(x);
- // arr[i][j]++;
- }
- ll ahasz = 0;
- for(int j = 1; j <= xn; j++)
- ahasz = (ahasz*prime+arr[i][j])%mod;
- for(int j = 1; j <= xn; j++)
- keks[xn-1].insert(gethasz(xn, i, j, ahasz));
- }
- while(m--){
- int xn;
- scanf("%d", &xn);
- vi ac;
- ac.reserve(xn+3);
- ll allhasz = 0;
- ac.pb(0);
- for(int i = 1; i <= xn; i++){
- int x;
- scanf("%d", &x);
- ac.pb(x);
- // ac[i]++;
- allhasz = (allhasz*prime+ac[i])%mod;
- }
- bool ans = 0;
- for(int i = 1; i <= xn; i++){
- int h = xn-i;
- int szuk1 = (mod+allhasz-(1LL*ac[i]*primes[h])%mod)%mod;
- int szuk2 = (mod2+allhasz-(1LL*ac[i]*primes[h])%mod2)%mod2;
- if(keks[xn-1].find(mp(szuk1, szuk2)) != keks[xn-1].end())ans = 1;
- }
- if(ans)printf("TAK\n");
- else printf("NIE\n");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement