Submission #1154309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154309		abcdxyz123	Matching (CEOI11_mat)	C++17	100 / 100	485 ms	34756 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 maxn 1000005
using namespace std;
const int Base=13;
int n,m;
int s[maxn];
int h[maxn];
int pw[maxn];
struct
{
    pi s[2*maxn];
    pi Merge(pi &X,pi &Y)
    {
        pi Z;
        if(X.se==0)return Y;
        if(Y.se==0)return X;
        Z.fi=X.fi*pw[Y.se]+Y.fi;
        Z.se=X.se+Y.se;
        return Z;
    }
    void update(int p, pi val)
    {
        for(s[p+=m]=val;p>>=1;)
        {
            s[p]=Merge(s[p<<1],s[p <<1|1]);
        }
    }
    int get(int l,int r)
    {
        pi resL = {0,0};
        pi resR = {0,0};
        for (l += m, r += m + 1; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1) resL=Merge(resL, s[l++]);
            if (r & 1) resR=Merge(s[--r],resR);
        }
        return Merge(resL,resR).fi;
    }
///
} Hash;
int N;
int tmp[maxn];
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];
        tmp[i]=h[i];
    }
    sort(tmp+1,tmp+m+1);
    for(int i=1; i<=m; i++)
    {
        h[i]=lower_bound(tmp+1,tmp+m+1,h[i])-tmp;
    }
    for(int i=1; i<n; i++)Hash.update(h[i],{i,1});
    for(int i=n; i<=m; i++)
    {
        Hash.update(h[i],{i,1});
        if(pattern==Hash.get(1,m))tmp[++N]=i-n+1;
        Hash.update(h[i-n+1],{0,0});
        pattern+=add;
    }
    cout<<N<<'\n';
    for(int i=1; i<=N; i++)cout<<tmp[i]<<' ';
    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