Submission #167660

#	Time	Username	Problem	Language	Result	Execution time	Memory
167660		bicsi	Matching (CEOI11_mat)	C++14	100 / 100	1459 ms	46056 KiB

mat

#include <bits/stdc++.h>

using namespace std;

int main() {
  int m, n; cin >> m >> n;
  
  vector<int> p(m), pos(m);
  for (int i = 0; i < m; ++i) { 
    int x; cin >> x; --x;
    p[x] = i;
    pos[i] = x;
  }

  vector<int> t(n);
  for (int i = 0; i < n; ++i)
    cin >> t[i];
  
  vector<int> lo(m, -1), hi(m, -1), pi(m + 1, -1);
  auto advance = [&](vector<int>& v, int i, int j) {
    while (j != -1) {
      if (lo[j] != -1 && v[i] < v[i - lo[j]]) { 
        j = pi[j]; 
        continue; 
      }
      if (hi[j] != -1 && v[i] > v[i - hi[j]]) { 
        j = pi[j]; 
        continue; 
      }
      break;
    }
    return j + 1;
  };
    
  vector<int> nxt(m, -1), prv(m, -1);
  for (int i = 0; i < m; ++i) {
    if (i > 0) prv[i] = i - 1;
    if (i + 1 < m) nxt[i] = i + 1;
  }

  for (int i = m - 1; i >= 0; --i) {
    int pr = prv[p[i]], nx = nxt[p[i]];
    if (pr != -1) lo[i] = i - pos[pr];
    if (nx != -1) hi[i] = i - pos[nx];
    if (pr != -1) nxt[pr] = nx;
    if (nx != -1) prv[nx] = pr;
  }

  for (int i = 0; i < m; ++i) {
    pi[i + 1] = advance(p, i, pi[i]);
  }

  vector<int> ans;
  int j = 0;
  for (int i = 0; i < n; ++i) {
    j = advance(t, i, j);
    if (j == m) {
      ans.push_back(i);
      j = pi[j];
    }
  }

  cout << ans.size() << endl;
  for (auto x : ans) {
    cout << x - m + 2 << " ";
  }
  cout << endl;

  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