Submission #413412

#	Time	Username	Problem	Language	Result	Execution time	Memory
413412		Bench0310	Matching (CEOI11_mat)	C++17	36 / 100	2096 ms	22364 KiB

mat

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    vector<int> s(n+1,0);
    for(int i=1;i<=n;i++) cin >> s[i];
    vector<int> h(m+1,0);
    for(int i=1;i<=m;i++) cin >> h[i];
    deque<int> d;
    auto add=[&](int i)
    {
        while(!d.empty()&&h[d.back()]>h[i]) d.pop_back();
        d.push_back(i);
    };
    auto rm=[&](int i)
    {
        if(!d.empty()&&d.front()==i) d.pop_front();
    };
    vector<int> res;
    auto ch=[&](int l)
    {
        vector<array<int,2>> v;
        for(int i=l;i<=l+n-1;i++) v.push_back({h[i],i-l+1});
        sort(v.begin(),v.end());
        bool ok=1;
        for(int i=0;i<n;i++) ok&=(v[i][1]==s[i+1]);
        if(ok) res.push_back(l);
    };
    for(int i=1;i<n;i++) add(i);
    for(int i=n;i<=m;i++)
    {
        add(i);
        int l=i-n+1;
        if(l+s[1]-1==d.front()) ch(l);
        rm(l);
    }
    cout << res.size() << "\n";
    for(int a:res) cout << a << " ";
    cout << "\n";
    return 0;
}

• 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