Submission #1187053

#TimeUsernameProblemLanguageResultExecution timeMemory
1187053aminjon__Matching (CEOI11_mat)C++17
63 / 100
349 ms62020 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define endl '\n' typedef unsigned int uint; typedef unsigned int ll; typedef long double ld; typedef unsigned long long ull; using namespace std; const ll maxn = 1e6; const ll modd = 65537 ; const ll modd2 = 65539; const ll p1 = 10007 ; const ll p2 = 10009; ll P1[maxn + 1], P2[maxn + 1]; ll M; ll f_H1(vector<ll> &A) { ll res = 0; for (int i = 0; i < A.size(); i++) { res += (A[i]%modd * P1[i]) % modd; res %= modd; } return res; } ll f_H2(vector<ll> &A) { ll res = 0; for (int i = 0; i < A.size(); i++) { res += (A[i]%modd2 * P2[i]) % modd2; res %= modd2; } return res; } ll h1[(1LL<<19)*3]; ll h2[(1LL<<19)*3]; ll sz[(1LL<<19)*3]; ll ans[(1LL<<19)*3]; map<ll, ll> mp; void update(ll need, ll val) { ll cur = M + need - 1; h1[cur] =(val%modd); h2[cur] =(val%modd2); sz[cur] = (val != 0); cur/=2; while(cur){ h1[cur] = (h1[cur+cur] + (h1[cur+cur+1] * P1[ sz[cur+cur] ])%modd)%modd; h2[cur] = (h2[cur+cur] + (h2[cur+cur+1] * P2[ sz[cur+cur] ])%modd2)%modd2; sz[cur]=sz[cur+1+cur]+sz[cur+cur]; cur/=2; } } signed main() { ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); ll n, m; cin >> n >> m; vector<ll>a(n+1) , b(m+1); P1[0] = P2[0] = 1; ll add1 = 1, add2 = 1; for (int i = 1; i <= 1 + n; i++) { P1[i] = (P1[i - 1] * p1) % modd; P2[i] = (P2[i - 1] * p2) % modd2; if (i < n) { add1 = (add1 + P1[i]) % modd; add2 = (add2 + P2[i]) % modd2; } } M =m; if( (m & (m-1))){ M = (1 << ll(log2(m)+1) ); } for (int i = 0; i < n; i++) cin >> a[i]; for (int j = 0; j < m; j++) { cin >> b[j]; mp[b[j]]; } int ind = 0; for (auto &g : mp) { ind++; g.second = ind; } ll Hx1 = f_H1(a); ll Hx2 = f_H2(a); ll kol = 0; ll __sz = 0; for (int j = 0; j < m; j++) { update(mp[b[j]], j + 1); if (sz[1] > n) { update(mp[b[j - n]], 0); Hx1 = (Hx1 + add1) % modd; Hx2 = (Hx2 + add2) % modd2; } if (sz[1] < n) continue; if (h1[1] == Hx1 && h2[1] == Hx2) { __sz++; ans[__sz-1] = j-n+2; } } cout<<__sz<<endl; for(int i = 0;i < __sz;i++){ cout<<ans[i]<<' '; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...