Submission #1240666

#TimeUsernameProblemLanguageResultExecution timeMemory
1240666chuchucharlesMatching (CEOI11_mat)C++20
100 / 100
148 ms35644 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int n, m, idx[maxn], s[maxn << 1], lt[maxn], rt[maxn], pi[maxn << 1]; struct linked_list { int n, *l, *r; linked_list(int n_) : n(n_), l(new int[n_ + 5]), r(new int[n_ + 5]) { for (int i = 1; i <= n; i++) { l[i] = i - 1; r[i] = i + 1; } } void del(int i) { int l_ = l[i], r_ = r[i]; r[l_] = r_; l[r_] = l_; } }; bool check(int i, int j) { if (i == n + 1) return false; if (lt[i] && s[j - i + lt[i]] > s[j]) return false; if (rt[i] && s[j + rt[i] - i] < s[j]) return false; return true; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> idx[i]; s[idx[i]] = i; } s[n + 1] = 0; for (int i = n + 2; i <= n + 1 + m; i++) cin >> s[i]; linked_list lk(n); for (int i = n; i >= 1; i--) { lt[i] = idx[lk.l[s[i]]]; rt[i] = idx[lk.r[s[i]]]; lk.del(s[i]); } vector<int> ans(0); for (int i = 2; i <= n + m + 1; i++) { if (i == n + 1) continue; int tmp = pi[i - 1]; while (tmp > 0 && !check(tmp + 1, i)) tmp = pi[tmp]; if (check(tmp + 1, i)) pi[i] = tmp + 1; if (i > n + 1 && pi[i] == n) ans.push_back(i - 2 * n); } cout << (int)ans.size() << '\n'; for (auto c : ans) cout << c << " "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...