Submission #1240654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240654		tuankhoi	Matching (CEOI11_mat)	C++20	100 / 100	707 ms	31700 KiB

mat

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const int MAXN = 1e6 + 5;
int s[MAXN * 2], idx[MAXN], L[MAXN], R[MAXN], mx[MAXN], mn[MAXN];

void del(int val) {
  int l = L[val];
  int r = R[val];
  L[r] = l;
  R[l] = r;
}

int kmp[MAXN];
int n, m;

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> idx[i];
    s[idx[i]] = i;
    L[i] = i - 1;
    R[i] = i + 1;
  }
  s[n + 1] = 0;
  for (int i = n; i >= 1; i--) {
    mx[i] = idx[L[s[i]]];
    mn[i] = idx[R[s[i]]];
    del(s[i]);
  }
  for (int i = n + 2; i <= n + m + 1; i++) {
    cin >> s[i];
  }
  vector<int> ans;
  for (int i = 2; i <= n + m + 1; i++) {
    if (i == n + 1) continue;
    int k = kmp[i - 1];
    while (k > 0 && !check(k + 1, i)) k = kmp[k];
    if (check(k + 1, i)) kmp[i] = k + 1;
    if (i > n + 1 && kmp[i] == n) ans.emplace_back(i - 2 * n);
  }
  cout << ans.size() << '\n';
  for (int i : ans) cout << i << ' ';
  return 0;
}

• 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