# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
124167 | 2019-07-02T15:19:15 Z | pedy4000 | Matching (CEOI11_mat) | C++14 | 450 ms | 23800 KB |
#include <algorithm> #include <cstring> #include <iostream> #include <vector> using namespace std; const int MAX_N = 1e6 + 6; int n, m; int Arr[MAX_N]; int Brr[MAX_N]; int Crr[MAX_N]; int F[MAX_N]; int sm[MAX_N]; int bg[MAX_N]; vector <int> ans; bool can (int *list, int l, int r) { int ind = r - l; if (list[r] < list[l + sm[ind]]) return false; if (list[l + bg[ind]] < list[r]) return false; return true; } void KMP() { F[1] = 0; F[2] = 1; int ind = 1; for (int i = 3; i <= n; i++) { while (ind && !can(Arr, i - ind - 1 , i - 1)) ind = F[ind]; ind++; F[i] = ind; } } void processRel() { sm[Crr[0]] = Crr[0]; for (int i = 1; i < n; i++) { sm[Crr[i]] = Crr[i]; int ind = Crr[i - 1]; while (sm[ind] != ind && Crr[i] < ind) ind = sm[ind]; if (ind <= Crr[i]) sm[Crr[i]] = ind; } bg[Crr[n - 1]] = Crr[n - 1]; for (int i = n - 2; ~i; i--) { bg[Crr[i]] = Crr[i]; int ind = Crr[i + 1]; while (bg[ind] != ind && Crr[i] < ind) ind = bg[ind]; if (ind <= Crr[i]) bg[Crr[i]] = ind; } } void findMatching() { int L = 0, R = 0; while (L < m) { while (R + 1 < L + n && R + 1 < m && can(Brr, L, R + 1)) R++; if (R - L == n - 1) ans.push_back(L + 1); if (L == R) L++, R++; else L += R - L + 1 - F[R - L + 1]; } } int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &Crr[i]); Crr[i]--; Arr[Crr[i]] = i; } processRel(); for (int i = 0; i < m; i++) scanf("%d", &Brr[i]); KMP(); findMatching(); printf("%lu\n", ans.size()); for (int l: ans) printf("%d ", l); return 0; } // S --> 5:45
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 508 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 34 ms | 1912 KB | Output is correct |
2 | Correct | 29 ms | 1272 KB | Output is correct |
3 | Correct | 50 ms | 2040 KB | Output is correct |
4 | Correct | 52 ms | 2168 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 2568 KB | Output is correct |
2 | Correct | 41 ms | 1272 KB | Output is correct |
3 | Correct | 43 ms | 1912 KB | Output is correct |
4 | Correct | 48 ms | 3308 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 2548 KB | Output is correct |
2 | Correct | 37 ms | 2040 KB | Output is correct |
3 | Correct | 43 ms | 1784 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 217 ms | 9488 KB | Output is correct |
2 | Correct | 450 ms | 23800 KB | Output is correct |
3 | Correct | 153 ms | 4088 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 217 ms | 10220 KB | Output is correct |
2 | Correct | 165 ms | 4384 KB | Output is correct |
3 | Correct | 399 ms | 22908 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 197 ms | 6320 KB | Output is correct |
2 | Correct | 236 ms | 15244 KB | Output is correct |
3 | Correct | 198 ms | 5760 KB | Output is correct |
4 | Correct | 311 ms | 23800 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 184 ms | 7380 KB | Output is correct |
2 | Correct | 202 ms | 5936 KB | Output is correct |
3 | Correct | 88 ms | 4272 KB | Output is correct |
4 | Correct | 316 ms | 21812 KB | Output is correct |