Submission #1221585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221585		DangKhoizzzz	Matching (CEOI11_mat)	C++20	100 / 100	845 ms	54480 KiB

mat

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 9;
const int base = 1e6 + 7;

int mul(int x , int y) {return (1ll*x*y)%mod;}
int add(int x , int y) {return (x+y)%mod;}

int power[maxn];

struct node
{
    int hsh , cnt;

    node()
    {
        hsh = 0 , cnt = 0;
    }
};

node merging (node L , node R)
{
    node res;
    res.cnt = L.cnt + R.cnt;
    res.hsh = add(mul(L.hsh,power[R.cnt]) , R.hsh);
    return res;
}

node st[maxn*4];

void update(int id , int l , int r , int pos , int val , int c)
{
    if(l > pos || r < pos) return;
    if(l == r)
    {
        st[id].hsh = val;
        st[id].cnt = c;
        return;
    }
    int mid = (l+r) >> 1;
    update(id*2 , l , mid , pos , val , c);
    update(id*2+1 , mid+1 , r , pos , val , c);
    st[id] = merging(st[id*2] , st[id*2+1]);
}

int n , m , a[maxn] , b[maxn];

void compress()
{
    vector <int> val;
    for(int i = 1; i <= m; i++) val.push_back(b[i]);
    sort(val.begin() , val.end());
    for(int i = 1; i <= m; i++)
    {
        b[i] = upper_bound(val.begin() , val.end() , b[i]) - val.begin();
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    power[0] = 1;
    for(int i = 1; i < maxn; i++) power[i] = mul(power[i-1] , base);
    compress();

    int v_hsh = 0, check = 0;

    for(int i = 0; i < n; i++)
    {
        v_hsh = add(v_hsh , power[n-i-1]);
        check = add(check , mul(power[n-i-1] , a[i+1]));
    }

    vector <int> ans;

    for(int i = 1; i <= m; i++)
    {
        update(1 , 1 , m , b[i] , i , 1);

        if(i > n) update(1 , 1 , m , b[i-n] , 0 , 0);
        
        if(i >= n)
        {
            assert(st[1].cnt == n);

            if(st[1].hsh == check)
            {
                ans.push_back(i-n+1);
            }
            check = add(check , v_hsh);
        }
    }
    cout << ans.size() << '\n';
    for(int x: ans) cout << x << ' ';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

mat.cpp:10:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   10 | const int INF = 1e18;
      |                 ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10