# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
227789 | 2020-04-28T19:49:18 Z | dolphingarlic | Matching (CEOI11_mat) | C++14 | 514 ms | 46100 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 640 KB | Output is correct |
2 | Correct | 8 ms | 512 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 640 KB | Output is correct |
2 | Correct | 8 ms | 512 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 2168 KB | Output is correct |
2 | Correct | 32 ms | 1272 KB | Output is correct |
3 | Correct | 54 ms | 2552 KB | Output is correct |
4 | Correct | 54 ms | 2552 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 2936 KB | Output is correct |
2 | Correct | 47 ms | 1400 KB | Output is correct |
3 | Correct | 46 ms | 2040 KB | Output is correct |
4 | Correct | 50 ms | 3308 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 2936 KB | Output is correct |
2 | Correct | 38 ms | 2432 KB | Output is correct |
3 | Correct | 45 ms | 2044 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 227 ms | 11380 KB | Output is correct |
2 | Correct | 514 ms | 41696 KB | Output is correct |
3 | Correct | 164 ms | 11896 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 223 ms | 12664 KB | Output is correct |
2 | Correct | 166 ms | 4344 KB | Output is correct |
3 | Correct | 495 ms | 40936 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 181 ms | 6640 KB | Output is correct |
2 | Correct | 230 ms | 15196 KB | Output is correct |
3 | Correct | 208 ms | 6440 KB | Output is correct |
4 | Correct | 309 ms | 46100 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 183 ms | 8304 KB | Output is correct |
2 | Correct | 215 ms | 6384 KB | Output is correct |
3 | Correct | 89 ms | 5112 KB | Output is correct |
4 | Correct | 338 ms | 35040 KB | Output is correct |