Submission #1151765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151765		abcdxyz123	Matching (CEOI11_mat)	C++17	100 / 100	591 ms	39436 KiB

mat

#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define fi first
#define se second
#define mod 1000000007
#define maxn 1000005
using namespace std;
const int Base=1000003;
int n,m;
int s[maxn];
int h[maxn];
int pw[maxn];
void Add(int &x,int y)
{
    x+=y;
    if(x>=mod)x-=mod;
}
struct
{
    pi s[4*maxn];
    void update(int k,int val)
    {
        int r=1;
        int lo=1;
        int hi=m;
        while(true)
        {
            if(lo==hi)
            {
                if(val)
                {
                    s[r]= {val,1};
                }
                else
                {
                    s[r]= {0,0};
                }
                break;
            }
            int mid=(lo+hi)/2;
            if(k<=mid)r=2*r,hi=mid;
            else r=2*r+1,lo=mid+1;
        }

        while(true)
        {
            r/=2;
            s[r].fi=s[2*r].fi*pw[s[2*r+1].se]+s[2*r+1].fi;
            s[r].se=s[2*r].se+s[2*r+1].se;
            if(r==1)break;
        }
    }

} Hash;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    pw[0]=1;
    for(int i=1; i<=m; i++)
    {
        pw[i]=pw[i-1]*Base;
    }
    int pattern=0;
    int add=0;
    for(int i=1; i<=n; i++)
    {
        cin>>s[i];
        pattern=pattern*Base+s[i];
        add+=pw[n-i];
    }
    vector<int>val;
    for(int i=1; i<=m; i++)
    {
        cin>>h[i];
        val.push_back(h[i]);
    }
    sort(all(val));
    for(int i=1; i<=m; i++)
    {
        h[i]=lower_bound(all(val),h[i])-val.begin()+1;
    }
    for(int i=1; i<n; i++)Hash.update(h[i],i);
    vector<int>ans;
    for(int i=n; i<=m; i++)
    {
        Hash.update(h[i],i);
        if(pattern==Hash.s[1].fi)ans.push_back(i-n+1);
        Hash.update(h[i-n+1],0);
        pattern+=add;
    }
    cout<<ans.size()<<'\n';
    for(int x:ans)cout<<x<<' ';
    return 0;

}
/*
Vi tri  -> Thu tu gia tri
*/

• 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