Submission #171945

#	Time	Username	Problem	Language	Result	Execution time	Memory
171945		AlexPop28	Matching (CEOI11_mat)	C++11	81 / 100	1898 ms	65540 KiB

mat

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

using namespace std;

bool Match(int k, int i, const vector<int> &p,
  const vector<int> &small, const vector<int> &big) {
  
  bool ret = true;
  ret &= big[k] == -1 || p[i] < p[i - k + big[k]];
  ret &= small[k] == -1 || p[i] > p[i - k + small[k]];
  return ret;
}

vector<int> GetPi(const vector<int> &p,
  const vector<int> &small, const vector<int> &big) {

  int n = p.size();
  vector<int> pi(n); 
  pi[0] = 0;
  int k = 0;
  for (int i = 1; i < n; ++i) {
    while (k != 0 && !Match(k, i, p, small, big)) k = pi[k - 1];
    if (Match(k, i, p, small, big)) ++k;
    pi[i] = k;
  }
  return move(pi);
}

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

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

  auto Comp = [&](int a, int b) {
    return p[a] < p[b];
  };
  vector<int> big(n, -1), small(n, -1);
  set<int, decltype(Comp)> vals(Comp);
  vals.emplace(0);
  for (int i = 1; i < n; ++i) {
    auto it = vals.emplace(i).first;
    if (it != vals.begin()) small[i] = *prev(it);
    if (next(it) != vals.end()) big[i] = *next(it);
  }

  auto pi = GetPi(p, small, big);
  vector<int> text(m);
  for (int i = 0; i < m; ++i) {
    cin >> text[i];
  }

  vector<int> ans;
  int k = 0;
  for (int i = 0; i < m; ++i) {
    while (k != 0 && !Match(k, i, text, small, big)) k = pi[k - 1];
    if (Match(k, i, text, small, big)) ++k;
    if (k == n) {
      ans.emplace_back(i - n + 1);
      k = pi[k - 1];
    }
  }

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