제출 #1186174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186174		HeartBreakKid	Matching (CEOI11_mat)	C++20	0 / 100	2096 ms	25072 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 (j > size_pattern) && ((ind_less == -1 || s[ind_less] < s[j]) &&
                                (ind_greater == -1 || s[ind_greater] > s[j]));
}

void z_function(const std::vector<int32_t>& s) {
  int64_t s_size = s.size();
  std::vector<int64_t> z(s_size, 0);
  int64_t l = 0;
  int64_t r = 0;
  for (int64_t i = 1; i < s_size; ++i) {
    if (i > r) {
      int64_t k = 0, j = 0;
      while (i + k < s_size && Ok(s, i + k, j + k)) {
        ++k;
      }
      l = i;
      r = i + k - 1;
      z[i] = k;
      continue;
    }
    z[i] = std::min(r - i + 1, z[i - l]);
    int64_t j = 0;
    while (i + z[i] < s_size && Ok(s, i + z[i], j + z[i])) {
      ++z[i];
    }
    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  // for (int64_t i = 0; i < s.size(); ++i) {
  //   std::cout << s[i] << " ";
  // }
  // std::cout << std::endl;
  for (int64_t i = 0; i < z.size(); ++i) {
    // std::cout << z[i] << " ";
    if (z[i] == size_pattern) {
      ans.push_back(i - size_pattern);
    }
  }
  // std::cout << std::endl;
}
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);
  }

  z_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