# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
227790 | 2020-04-28T19:50:11 Z | dolphingarlic | Matching (CEOI11_mat) | C++14 | 572 ms | 31612 KB |
#include <bits/stdc++.h> using namespace std; const int N = 1e6; int p[N], h[N], pos[N], prv[N], nxt[N], l_pred[N], l_succ[N], partial[N]; vector<int> matches; inline bool can_extend(int i, int j, int *v) { return ((!l_pred[j + 1] || v[i - l_pred[j + 1]] < v[i]) && (!l_succ[j + 1] || v[i] < v[i - l_succ[j + 1]])); } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); p[x - 1] = i; pos[i] = x - 1; prv[i] = i - 1, nxt[i] = i + 1; } for (int i = 0; i < m; i++) scanf("%d", h + i); for (int i = n - 1; ~i; i--) { if (~prv[p[i]]) { l_pred[i] = i - pos[prv[p[i]]]; nxt[prv[p[i]]] = nxt[p[i]]; } if (nxt[p[i]] != n) { l_succ[i] = i - pos[nxt[p[i]]]; prv[nxt[p[i]]] = prv[p[i]]; } } for (int i = 1, j = partial[0] = -1; i < n; i++) { while (~j && !can_extend(i, j, p)) j = partial[j]; if (can_extend(i, j, p)) j++; partial[i] = j; } for (int i = 0, j = -1; i < m; i++) { while (~j && !can_extend(i, j, h)) j = partial[j]; if (can_extend(i, j, h)) j++; if (j == n - 1) { matches.push_back(i - n + 2); j = partial[j]; } } printf("%d\n", matches.size()); for (int i : matches) printf("%d ", i); printf("\n"); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 512 KB | Output is correct |
2 | Correct | 8 ms | 548 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 640 KB | Output is correct |
2 | Correct | 8 ms | 512 KB | Output is correct |
3 | Correct | 5 ms | 428 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 2168 KB | Output is correct |
2 | Correct | 31 ms | 1280 KB | Output is correct |
3 | Correct | 54 ms | 2552 KB | Output is correct |
4 | Correct | 54 ms | 2552 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 3016 KB | Output is correct |
2 | Correct | 46 ms | 1272 KB | Output is correct |
3 | Correct | 46 ms | 2040 KB | Output is correct |
4 | Correct | 50 ms | 3436 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 2932 KB | Output is correct |
2 | Correct | 41 ms | 2424 KB | Output is correct |
3 | Correct | 46 ms | 2048 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 227 ms | 11332 KB | Output is correct |
2 | Correct | 572 ms | 31560 KB | Output is correct |
3 | Correct | 159 ms | 4216 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 225 ms | 12664 KB | Output is correct |
2 | Correct | 165 ms | 4216 KB | Output is correct |
3 | Correct | 464 ms | 30360 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 182 ms | 6640 KB | Output is correct |
2 | Correct | 234 ms | 15196 KB | Output is correct |
3 | Correct | 207 ms | 6392 KB | Output is correct |
4 | Correct | 307 ms | 31612 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 189 ms | 8176 KB | Output is correct |
2 | Correct | 217 ms | 6392 KB | Output is correct |
3 | Correct | 94 ms | 5112 KB | Output is correct |
4 | Correct | 332 ms | 28880 KB | Output is correct |