Submission #1240688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240688		bncodero_o123	Matching (CEOI11_mat)	C++20	100 / 100	157 ms	35460 KiB

mat

#include <bits/stdc++.h>
#define ll long long
#define name "code"
using namespace std;

const int max_n= 1e6;
int n, m, idx[max_n + 2];
int s[2 * max_n + 2], MIN[max_n + 2], MAX[max_n + 2];
int kmp[2 * max_n + 5];

int L[max_n + 2], R[max_n + 2];

void init() {
    for(int i= 1; i <= n; ++i)
        L[i]= i - 1, R[i]= i + 1;
}

void del(int x) {
    int _l= L[x], _r= R[x];
    R[_l]= _r, L[_r]= _l;
}

bool check(int i, int j) {
    if(i == n + 1) return 0;
    if(MAX[i] && s[j - i + MAX[i]] > s[j]) return 0;
    if(MIN[i] && s[j - i + MIN[i]] < s[j]) return 0;
    return 1;
}

void solve() {
    cin >> n >> m;
    for(int i= 1; i <= n; ++i) {
        cin >> idx[i];
        s[idx[i]]= i;
    }
    for(int i= n + 2; i <= n + m + 1; ++i) cin >> s[i];

    init();
    for(int i= n; i > 0; --i) {
        MAX[i]= idx[L[s[i]]];
        MIN[i]= idx[R[s[i]]];
        del(s[i]);
    }

    vector<int> ans;
    for(int i= 2; i <= n + m + 1; ++i)
        if(i != n + 1) {
            int j= kmp[i - 1];
            while(j && !check(j + 1, i)) j= kmp[j];
            kmp[i]= j += check(j + 1, i);
            if(i > n && j == n) ans.push_back(i - 2 * n);
        }

    cout << ans.size() << '\n';
    for(int x : ans) cout << x << ' ';
}

signed main() {
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    int T= 1;
    for(; T; --T) solve();

    return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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