Submission #171921

#	Time	Username	Problem	Language	Result	Execution time	Memory
171921		AlexPop28	Matching (CEOI11_mat)	C++11	63 / 100	565 ms	65540 KiB

mat

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

set<int> Solve(int patt_size, const vector<int> &p) {
  int n = p.size();
  vector<int> pi(n), big(n, -1), small(n, -1);
  pi[0] = 0;
  auto Match = [&](int k, int i) {
    bool ret = true;
    int bg = big[k], sm = small[k];
    ret &= bg == -1 || p[i] < p[i - k + bg];
    ret &= sm == -1 || p[i] > p[i - k + sm];
    return ret;
  };
  set<pair<int, int>> vals;
  vals.emplace(p[0], 0);
  set<int> ans;
  // for (int i = 0; i < n; ++i) dbg() p[i] << ' '; dbg() endl;
  for (int i = 1; i < n; ++i) {
    auto it = vals.emplace(p[i], i).first;
    if (it != vals.begin()) {
      small[i] = prev(it)->second;   
    }
    if (next(it) != vals.end()) {
      big[i] = next(it)->second;
    }
    // dbg() name(i) name(small[i]) name(big[i]) endl;
    int k = pi[i - 1];
    while (k != 0 && !Match(k, i)) k = pi[k - 1];
    if (Match(k, i)) ++k;
    pi[i] = k;
    if (pi[i] == patt_size && i >= 2 * patt_size) {
      ans.emplace(i - 2 * patt_size);
      pi[i] = pi[pi[i] - 1];
    }
    // dbg() name(i) name(pi[i]) endl;
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, m; cin >> n >> m;
  vector<int> p(n + m + 1);
  for (int i = 0; i < n; ++i) {
    int s; cin >> s; --s;
    p[s] = i;
  }
  p[n] = -1;
  for (int i = n + 1; i < n + m + 1; ++i) {
    cin >> p[i]; p[i] += n;
  }
  auto ans0 = Solve(n, p);
  p[n] = (int)2e9;
  auto ans1 = Solve(n, p);
  vector<int> ans;
  for (auto &x : ans0) {
    if (ans1.find(x) != ans1.end()) {
      ans.emplace_back(x);
    }
  }
  cout << ans.size() << endl;
  for (int &x : ans) {
    cout << 1 + x << ' ';
  }
  cout << endl;
}

• 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: 0 / 10