제출 #1259382

#제출 시각아이디문제언어결과실행 시간메모리
1259382jesperMatching (CEOI11_mat)C++20
18 / 100
2095 ms22796 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...