Submission #1105271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105271		flashmt	Matching (CEOI11_mat)	C++17	100 / 100	180 ms	47944 KiB

mat

#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n), pos(n), l(n), r(n);
  for (int i = 0; i < n; i++)
  {
    cin >> pos[i];
    a[--pos[i]] = i;
    l[i] = i - 1;
    r[i] = i + 1;
  }
  vector<int> b(m);
  for (int &x : b)
    cin >> x;

  vector<int> prev(n, -1), next(n, -1);
  for (int i = n - 1; i >= 0; i--)
  {
    int x = a[i];
    if (l[x] >= 0)
      prev[i] = pos[l[x]];
    if (r[x] < n)
      next[i] = pos[r[x]];
    if (l[x] >= 0)
      r[l[x]] = r[x];
    if (r[x] < n)
      l[r[x]] = l[x];
  }

  auto match = [&](vector<int> &a, int i, int j)
  {
    return (prev[j] < 0 || a[i] > a[i - j + prev[j]]) && (next[j] < 0 || a[i] < a[i - j + next[j]]);
  };

  vector<int> pre(n, -1);
  for (int i = 0, j = -1; i < n; i++)
  {
    while (j >= 0 && !match(a, i, j))
      j = j ? pre[j - 1] + 1 : -1;
    pre[i] = j++;
  }

  vector<int> ans;
  for (int i = 0, j = 0; i < m; i++)
  {
    while (j >= 0 && !match(b, i, j))
      j = j ? pre[j - 1] + 1 : -1;
    if (j == n - 1)
    {
      j = pre[j];
      ans.push_back(i - n + 1);
    }
    j++;
  }

  cout << size(ans) << endl;
  for (int x : ans)
    cout << x + 1 << ' ';
}

• 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