Submission #1116938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116938		duckindog	Matching (CEOI11_mat)	C++17	100 / 100	824 ms	65536 KiB

mat

#include <bits/stdc++.h>

using namespace std;

const int N = 1'000'000 + 10;
int n, m;
int b[N], a[N];

using ull = unsigned long long;
const ull base = 19937;
ull pw[N];

pair<ull, int> f[N << 2];
void update(int s, int l, int r, int p, int value) { 
  if (p < l || p > r) return;
  if (l == r) { 
    if (!value) f[s] = {0, 0};
    else f[s] = {value, 1};
    return;
  }
  int mid = (l + r) >> 1;
  update(s << 1, l, mid, p, value); update(s << 1 | 1, mid + 1, r, p, value);
  f[s].first = f[s << 1].first * pw[f[s << 1 | 1].second] + f[s << 1 | 1].first;
  f[s].second = f[s << 1].second + f[s << 1 | 1].second;
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> b[i];
  for (int i = 1; i <= m; ++i) cin >> a[i];

  vector<int> allValue(a + 1, a + m + 1);
  sort(allValue.begin(), allValue.end());
  for (int i = 1; i <= m; ++i) 
    a[i] = upper_bound(allValue.begin(), allValue.end(), a[i]) - allValue.begin();

  ull hashAnswer = 0, sum = 0;
  pw[0] = 1;
  for (int i = 1; i <= n; ++i) { 
    pw[i] = pw[i - 1] * base;
    hashAnswer = hashAnswer * base + b[i];
    sum = sum + pw[i - 1];
  }
  for (int i = 1; i <= n; ++i) update(1, 1, m, a[i], i);
  
  vector<int> answer;
  for (int i = n; i <= m; ++i) { 
    if (hashAnswer == f[1].first) answer.push_back(i - n + 1);
    
    update(1, 1, m, a[i - n + 1], 0);
    update(1, 1, m, a[i + 1], i + 1);
    hashAnswer += sum;
  }

  cout << answer.size() << "\n";
  for (const auto& x : answer) cout << x << " ";
  cout << "\n";
}

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