Submission #269877

#	Time	Username	Problem	Language	Result	Execution time	Memory
269877		stefantaga	Matching (CEOI11_mat)	C++14	36 / 100	2099 ms	64716 KiB

mat

#include <bits/stdc++.h>
#define MOD 1000000007
#define baza 37
using namespace std;
int ub (int x)
{
    return x&(-x);
}
int m,aib[1000005];
void update (int poz,int val)
{
    int i;
    for (i=poz;i<=m;i+=ub(i))
    {
        aib[i]+=val;
    }
}
int query (int poz)
{
    int suma=0,i;
    for (i=poz;i>=1;i-=ub(i))
    {
        suma+=aib[i];
    }
    return suma;
}
long long ridput (long long a,long long b)
{
    if (b==0)
    {
        return 1;
    }
    long long rez=ridput(a,b/2);
    if (b%2==0)
    {
        return (rez*rez)%MOD;
    }
    return ((rez*rez)%MOD*a)%MOD;
}
int n,i,v[1000005],v2[1000005],ok,solutie,j,pozitie,fr[1000005];
vector <int> sol;
map <int,int> map1;
int nr;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
        fr[v[i]]=i;
    }
    for (i=1;i<=m;i++)
    {
        cin>>v2[i];
        map1[v2[i]]=1;
    }
    nr=0;
    for (auto ind : map1)
    {
        nr++;
        map1[ind.first]=nr;
    }
    for (i=1;i<=m;i++)
    {
        v2[i]=map1[v2[i]];
    }
    for (i=1;i<=n;i++)
    {
        update(v2[i],1);
    }
    nr=0;
    ok=1;
    for (i=1;i<=n;i++)
    {
        pozitie=query(v2[i]);
        if (pozitie!=fr[i])
        {
            ok=0;
            break;
        }
    }
    if (ok==1)
    {
        solutie++;
        sol.push_back(1);
    }
    for (i=2;i<=m-n+1;i++)
    {
        update(v2[i-1],-1);
        update(v2[i+n-1],1);
        ok=1;
        for (j=i;j<=i+n-1;j++)
        {
            pozitie=query(v2[j]);
            if (pozitie!=fr[j-i+1])
            {
                ok=0;
                break;
            }
        }
        if (ok==1)
        {
            solutie++;
        sol.push_back(i);
        }
    }
    cout<<solutie<<'\n';
    for (i=0;i<sol.size();i++)
    {
        cout<<sol[i]<<" ";
    }
    return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:114:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     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: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10