제출 #879303

#제출 시각아이디문제언어결과실행 시간메모리
879303serifefedartarMatching (CEOI11_mat)C++17
0 / 100
20 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); #define s second #define f first typedef long long ll; const ll MOD = 1e9 + 9; const ll LOGN = 21; const ll MAXN = 1e6 + 100; struct Node { ll hash; int cnt; Node() : hash(0), cnt(0) { } }; const ll P = 3412113; vector<int> A, B, cc; Node sg[4 * MAXN]; ll powP[MAXN]; Node merge(Node a, Node b) { Node new_node; new_node.cnt = a.cnt + b.cnt; new_node.hash = (a.hash * powP[b.cnt] + b.hash) % MOD; return new_node; } void update(int k, int a, int b, int pos, int val) { if (b < pos || a > pos) return ; if (a == b) { sg[k].hash = val; sg[k].cnt = (val != 0); return ; } update(2*k, a, (a+b)/2, pos, val); update(2*k+1, (a+b)/2+1, b, pos, val); sg[k] = merge(sg[2*k], sg[2*k+1]); } int main() { fast powP[0] = 1; for (int i = 1; i < MAXN; i++) powP[i] = (powP[i-1] * P) % MOD; int N, M; cin >> N >> M; A = vector<int>(N + 1); B = vector<int>(M + 1); for (int i = 1; i <= N; i++) cin >> A[i]; ll main_hash = 0; for (int i = 1; i <= N; i++) main_hash = (main_hash * P + A[i]) % MOD; for (int i = 1; i <= M; i++) { cin >> B[i]; cc.push_back(B[i]); } sort(cc.begin(), cc.end()); for (int i = 1; i <= M; i++) B[i] = upper_bound(cc.begin(), cc.end(), B[i]) - cc.begin(); ll sum = 0; for (int i = 0; i < N; i++) sum = (sum + powP[i]) % MOD; for (int i = 1; i < N; i++) update(1, 1, M + 10, B[i], i); vector<int> ans; for (int i = N; i <= M; i++) { update(1, 1, M + 10, B[i], i); ll hash_here = (sg[1].hash - (i - N) * sum % MOD + MOD) % MOD; if (hash_here == main_hash) ans.push_back(i - N + 1); update(1, 1, M + 10, B[i-N+1], 0); } cout << ans.size() << "\n"; for (auto u : ans) cout << u << " "; cout << "\n"; }
#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...