Submission #1186173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186173		HeartBreakKid	Matching (CEOI11_mat)	C++20	0 / 100	85 ms	20912 KiB

mat

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pk pop_back
#define yes std::cout << "YES\n"
#define no std::cout << "NO\n"
int32_t size_pattern;
int32_t size_text;
int32_t k;
constexpr int32_t kMod = 1e9 + 7;
std::unordered_map<int32_t, int32_t> mp;
std::string s;
std::vector<int64_t> ans;
std::vector<int64_t> less;
std::vector<int64_t> greater;

bool Ok(const std::vector<int32_t>& s, ll j, ll i) {
  if (i >= less.size()) {
    return false;
  }
  ll ind_less = less[i] == -1 ? -1 : j - (i - less[i]);
  ll ind_greater = greater[i] == -1 ? -1 : j - (i - greater[i]);
  return (i != size_pattern) && !(j - i <= size_pattern && size_pattern <= j) &&
         ((ind_less == -1 || s[ind_less] < s[j]) && (ind_greater == -1 || s[ind_greater] > s[j]));
}
std::vector<int> prefix_function(const std::vector<int32_t>& s) {
  int n = (int)s.size();
  std::vector<int> p(n, 0);
  for (int i = 1; i < n; i++) {
    int cur = p[i - 1];
    while (!Ok(s, i, cur) && cur > 0) cur = p[cur - 1];
    if (Ok(s, i, cur)) p[i] = cur + 1;
    if (p[i] == size_pattern) {
      ans.push_back(i - size_pattern * 2 + 1);
    }
  }
  return p;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);

  std::cin >> size_pattern >> size_text;
  std::vector<int32_t> pattern(size_pattern);
  for (int32_t i = 0; i < size_pattern; ++i) {
    int32_t x;
    std::cin >> x;
    pattern[x - 1] = i + 1;
  }
  less.resize(size_pattern, -1);
  greater.resize(size_pattern, -1);
  for (int32_t i = 1; i < size_pattern; ++i) {
    if (pattern[i - 1] > pattern[i]) {
      ll ind = i - 1;
      while (less[ind] != -1 && pattern[less[ind]] > pattern[i]) {
        ind = less[ind];
      }
      greater[i] = ind;
      less[i] = less[ind];
    } else {
      ll ind = i - 1;
      while (greater[ind] != -1 && pattern[greater[ind]] < pattern[i]) {
        ind = greater[ind];
      }
      less[i] = ind;
      greater[i] = greater[ind];
    }
  }
  std::vector<int32_t> text(size_text);
  for (int32_t i = 0; i < size_text; ++i) {
    std::cin >> text[i];
  }
  auto kmp = pattern;
  kmp.push_back(0);
  for (auto num : text) {
    kmp.push_back(num);
  }

  prefix_function(kmp);

  std::cout << ans.size() << "\n";
  for (auto x : ans) {
    std::cout << x << " ";
  }
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10