Submission #1259382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259382		jesper	Matching (CEOI11_mat)	C++20	18 / 100	2095 ms	22796 KiB

mat

#include <bits/stdc++.h>
using namespace std;

// Function to convert a sequence to relative order
vector<int> relative_order(const vector<int>& seq) {
    int n = seq.size();
    vector<int> order(n);
    vector<int> sorted = seq;
    sort(sorted.begin(), sorted.end());
    unordered_map<int,int> rank;
    for(int i=0;i<n;i++) rank[sorted[i]] = i;
    for(int i=0;i<n;i++) order[i] = rank[seq[i]];
    return order;
}

bool is_isomorphic(const vector<int>& a, const vector<int>& b) {
    int n = a.size();
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if((a[i]<a[j]) != (b[i]<b[j])) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> s(n), h(m);
    for(int i=0;i<n;i++) cin >> s[i];
    for(int i=0;i<m;i++) cin >> h[i];

    // Pattern as relative order
    vector<int> pattern(n);
    for(int i=0;i<n;i++) pattern[s[i]-1] = i;

    vector<int> result;

    for(int i=0;i<=m-n;i++) {
        vector<int> window(h.begin()+i, h.begin()+i+n);
        if(relative_order(window) == pattern)
            result.push_back(i+1); // 1-based index
    }

    cout << result.size() << "\n";
    for(int idx : result) cout << idx << " ";
    if(!result.empty()) cout << "\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 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