Submission #475588

#	Time	Username	Problem	Language	Result	Execution time	Memory
475588		stefantaga	Matching (CEOI11_mat)	C++14	63 / 100	1014 ms	65540 KiB

mat

#include <bits/stdc++.h>
#define baza 10000
#define MOD1 1000000007
#define MOD2 1000000013
using namespace std;
struct wow
{
    long long first,second,nr;
}arb[4000005];
long long p1[1000005],p2[1000005],ceau[1000005];
void update (int st,int dr,int nod,int poz,int val)
{
    if (st==dr)
    {
        arb[nod].first=arb[nod].second=val;
        if (val==0)
        {
            arb[nod].nr=0;
        }
        else
        {
            arb[nod].nr=1;
        }
        return ;
    }
    int mij=(st+dr)/2;
    if (poz<=mij)
    {
        update(st,mij,2*nod,poz,val);
    }
    else
    {
        update(mij+1,dr,2*nod+1,poz,val);
    }
    arb[nod].first=((arb[2*nod].first*p1[arb[2*nod+1].nr])%MOD1+arb[2*nod+1].first)%MOD1;
    arb[nod].second=((arb[2*nod].second*p2[arb[2*nod+1].nr])%MOD2+arb[2*nod+1].second)%MOD2;
    arb[nod].nr=arb[2*nod].nr+arb[2*nod+1].nr;
}
long long n,m,check1,check2,sum1,sum2,i,val1,val2,x;
pair <int,int> v[1000005];vector <int> sol;
int main()
{
    #ifdef HOME
    ifstream cin ("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>m>>n;
    for (i=1;i<=m;i++)
    {
        cin>>x;
        check1=(check1*baza+x)%MOD1;
        check2=(check2*baza+x)%MOD2;
    }
    p1[0]=1;p2[0]=1;
    for (i=1;i<=n;i++)
    {
        p1[i]=(p1[i-1]*baza)%MOD1;
        p2[i]=(p2[i-1]*baza)%MOD2;
    }
    for (i=0;i<m;i++)
    {
        sum1=(sum1+p1[i])%MOD1;
        sum2=(sum2+p2[i])%MOD2;
    }
    for (i=1;i<=n;i++)
    {
        cin>>v[i].first;
        v[i].second=i;
    }
    sort (v+1,v+n+1);
    for (i=1;i<=n;i++)
    {
        ceau[v[i].second]=i;
    }
    for (i=1;i<m;i++)
    {
        update(1,n,1,ceau[i],i);
    }
    for (i=m;i<=n;i++)
    {
        update(1,n,1,ceau[i],i);

        val1=(arb[1].first-(sum1*(i-m))%MOD1+MOD1)%MOD1;
        val2=(arb[1].second-(sum2*(i-m))%MOD2+MOD2)%MOD2;

        if (val1==check1&&val2==check2)
        {
            sol.push_back(i-m+1);
        }
        update(1,n,1,ceau[i-m+1],0);
    }
    cout<<sol.size()<<'\n';
    for (i=0;i<sol.size();i++)
    {
        cout<<sol[i]<<" ";
    }
    return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:93:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (i=0;i<sol.size();i++)
      |              ~^~~~~~~~~~~

• 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: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10