| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1186715 | HeartBreakKid | Matching (CEOI11_mat) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define endl '\n'
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
const ll maxn = 1e6;
const ll modd = 1e9 + 7;
const ll modd2 = 1e7 + 7;
const ll p1 = 1e6 + 1;
const ll p2 = 1e6 + 1;
ll P1[maxn + 1], P2[maxn + 1];
ll a[maxn + 1], b[maxn + 1];
ll f_H1(vector<ll> &A)
{
ll res = 0;
for (int i = 0; i < A.size(); i++)
{
res += (A[i] * 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] * P2[i]) % modd2;
res %= modd2;
}
return res;
}
struct Drvo
{
vector<ll> h1, h2, sz;
Drvo(ll n)
{
h1.resize(1 + n * 4);
h2.resize(1 + n * 4);
sz.resize(1 + n * 4);
}
void update(ll x, ll lx, ll rx, ll need, ll val)
{
if (lx > need || rx < need)
{
return;
}
if (lx == rx)
{
h1[x] = val;
h2[x] = val;
sz[x] = !!val;
return;
}
ll mid = (lx + rx) / 2;
update(x + x, lx, mid, need, val);
update(x + x + 1, mid + 1, rx, need, val);
h1[x] = (h1[x + x] + (P1[sz[x + x]] * h1[x + x + 1] % modd)) % modd;
h2[x] = (h2[x + x] + (P2[sz[x + x]] * h2[x + x + 1] % modd2)) % modd2;
sz[x] = sz[x + x] + sz[x + x + 1];
}
};
signed main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
ll n, m;
cin >> n >> m;
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;
}
}
map<ll, ll> mp;
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;
}
Drvo A(m + 1);
ll Hx1 = f_H1(a);
ll Hx2 = f_H2(a);
ll kol = 0;
vector<ll> ans;
for (int j = 0; j < m; j++)
{
A.update(1, 1, m, mp[b[j]], j + 1);
if (A.sz[1] > n)
{
A.update(1, 1, m, mp[b[j - n]], 0);
Hx1 = (Hx1 + add1) % modd;
Hx2 = (Hx2 + add2) % modd2;
}
if (A.sz[1] < n)
continue;
if (A.h1[1] == Hx1 && A.h2[1] == Hx2)
{
ans.push_back(j - n + 2);
}
}
cout << ans.size() << endl;
for (auto g : ans)
cout << g << ' ';
return 0;
}