Submission #167659

#	Time	Username	Problem	Language	Result	Execution time	Memory
167659		bicsi	Matching (CEOI11_mat)	C++14	73 / 100	2061 ms	65536 KiB

mat

#include <bits/stdc++.h>

using namespace std;

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

  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;
  };

  map<int, int> mmap;
  for (int i = 0; i < m; ++i) {
    auto it = mmap.insert({p[i], i}).first;
    if (it != mmap.begin()) lo[i] = i - prev(it)->second;
    if (next(it) != mmap.end()) hi[i] = i - next(it)->second;
    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: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 10 / 10