Submission #1240652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240652		tuankhoi	Matching (CEOI11_mat)	C++20	Compilation error	0 ms	0 KiB

mat

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const int MAXN = 1e6 + 5;
int s[MAXN * 2], index[MAXN], L[MAXN], R[MAXN], mx[MAXN], mn[MAXN];

void del(int val) {
  int l = L[val];
  int r = R[val];
  L[r] = l;
  R[l] = r;
}

int kmp[MAXN];
int n, m;

bool check(int i, int j) {
  if (i == n + 1) return 0;
  if (mx[i] && s[j - i + mx[i]] > s[j]) return 0;
  if (mn[i] && s[j - i + mn[i]] < s[j]) return 0;
  return 1;
}

int main() {
  #define NAME "test"
  if (fopen(NAME".inp", "r")) {
    freopen(NAME".inp", "r", stdin);
    freopen(NAME".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> index[i];
    s[index[i]] = i;
    L[i] = i - 1;
    R[i] = i + 1;
  }
  s[n + 1] = 0;
  for (int i = n; i >= 1; i--) {
    mx[i] = index[L[s[i]]];
    mn[i] = index[R[s[i]]];
    del(s[i]);
  }
  for (int i = n + 2; i <= n + m + 1; i++) {
    cin >> s[i];
  }
  vector<int> ans;
  for (int i = 2; i <= n + m + 1; i++) {
    if (i == n + 1) continue;
    int k = kmp[i - 1];
    while (k > 0 && !check(k + 1, i)) k = kmp[k];
    if (check(k + 1, i)) kmp[i] = k + 1;
    if (i > n + 1 && kmp[i] == n) ans.emplace_back(i - 2 * n);
  }
  cout << ans.size() << '\n';
  for (int i : ans) cout << i << ' ';
  return 0;
}

Compilation message (stderr)

mat.cpp:12:28: error: 'int index [1000005]' redeclared as different kind of entity
   12 | int s[MAXN * 2], index[MAXN], L[MAXN], R[MAXN], mx[MAXN], mn[MAXN];
      |                            ^
In file included from /usr/include/string.h:462,
                 from /usr/include/c++/11/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:48,
                 from mat.cpp:1:
/usr/include/strings.h:61:1: note: previous declaration 'const char* index(const char*, int)'
   61 | index (const char *__s, int __c) __THROW
      | ^~~~~
mat.cpp: In function 'int main()':
mat.cpp:41:17: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   41 |     cin >> index[i];
      |                 ^
mat.cpp:42:12: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   42 |     s[index[i]] = i;
      |            ^
mat.cpp:48:18: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   48 |     mx[i] = index[L[s[i]]];
      |                  ^
mat.cpp:49:18: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   49 |     mn[i] = index[R[s[i]]];
      |                  ^
mat.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen(NAME".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen(NAME".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~