제출 #1184970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184970		HeartBreakKid	Matching (CEOI11_mat)	C++20	0 / 100	397 ms	31420 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;
constexpr int32_t kBase = 37;
int32_t pows[1'000'005];

std::pair<int32_t, int32_t> tree[2'000'000 + 5];
std::pair<int32_t, int32_t> for_compress[1'000'000 + 5];

void Update(int position, int value,
            int cur_ind = 1, int left = 1,
            int right = size_text) {
  if (left > position || right < position) {
    return;
  }
  if (left == right) {
    tree[cur_ind] = {value, value != 0};
    // value == 0 только если мы удаляем это число
    return;
  }
  int32_t mid = (left + right) >> 1;

  Update(position, value, cur_ind * 2, left, mid);
  Update(position, value, cur_ind * 2 + 1, mid + 1, right);

  tree[cur_ind].second =
      tree[cur_ind * 2].second + tree[cur_ind * 2 + 1].second;
  tree[cur_ind].first = (tree[cur_ind * 2].first * 1LL *
                             pows[tree[cur_ind * 2 + 1].second] % kMod +
                         tree[cur_ind * 2 + 1].first) %
                        kMod;
}

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);
  pows[0] = 1;
  for (int32_t i = 1; i <= 1000005; i++) {
    pows[i] = (pows[i - 1] * 1LL * kBase) % kMod;
  }
  std::cin >> size_pattern >> size_text;
  std::vector<int32_t> pattern(size_pattern);

  int32_t hash_to_add{};
  int32_t need_hash{};
  for (int32_t i = 0; i < size_pattern; ++i) {
    std::cin >> pattern[i];
    hash_to_add = (hash_to_add + 0LL + pows[i]) % kMod;
    need_hash = (need_hash * 1LL * kBase + pattern[i]) % kMod;
  }

  for (int32_t i = 0; i < size_text; ++i) {
    std::cin >> for_compress[i].first;
    for_compress[i].second = i;
  }
  std::ranges::sort(for_compress);
  std::vector<int32_t> text(size_text);
  for (int32_t i = 0; i < size_text; ++i) {
    text[for_compress[i].second] = i + 1;
  }

  for (int32_t i = 0; i < size_pattern; ++i) {
    Update(text[i], i + 1);
  }
  std::vector<int32_t> ans;
  for (int32_t i = size_pattern; i < size_text; ++i) {
    // std::cout << tree[1].first << " " << need_hash << std::endl;
    if (tree[1].first == need_hash) {
      ans.push_back(i - size_pattern + 1);
    }
    Update(text[i - size_pattern], 0);
    Update(text[i], i + 1);
    need_hash += hash_to_add;
    need_hash %= kMod;
  }
  if (tree[1].first == need_hash) {
    ans.push_back(size_text - size_pattern + 1);
  }
  std::cout << ans.size() << '\n';
  for (auto ind : ans) {
    std::cout << ind << ' ';
  }
}

컴파일 시 표준 에러 (stderr) 메시지

mat.cpp: In function 'int main()':
mat.cpp:55:13: warning: iteration 1000004 invokes undefined behavior [-Waggressive-loop-optimizations]
   55 |     pows[i] = (pows[i - 1] * 1LL * kBase) % kMod;
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:54:25: note: within this loop
   54 |   for (int32_t i = 1; i <= 1000005; i++) {
      |                       ~~^~~~~~~~~~

• 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