# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
115550 | 2019-06-08T06:47:56 Z | gs14004 | Matching (CEOI11_mat) | C++17 | 646 ms | 48820 KB |
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <limits.h> #include <math.h> #include <time.h> #include <iostream> #include <functional> #include <numeric> #include <algorithm> #include <stack> #include <queue> #include <deque> #include <vector> #include <string> #include <bitset> #include <map> #include <set> using namespace std; typedef long long lint; typedef long double llf; typedef pair<int, int> pi; int n, m, a[1000005], b[1000005]; int lp[1000005], rp[1000005], fail[1000005]; bool ins1(int x, int p){ return a[x - lp[p]] <= a[x] && a[x] <= a[x - rp[p]]; } bool ins2(int x, int p){ return b[x - lp[p]] <= b[x] && b[x] <= b[x - rp[p]]; } int nxtl[1000005], nxtr[1000005], r[1000005]; int fl(int x){ if(x < 0) return x; return nxtl[x] = (nxtl[x] == x ? x : fl(nxtl[x])); } int fr(int x){ if(x >= n) return x; return nxtr[x] = (nxtr[x] == x ? x : fr(nxtr[x])); } int main(){ cin >> n >> m; for(int i=0; i<n; i++){ int v; scanf("%d",&v); a[v-1] = i; r[i] = v-1; nxtl[i] = nxtr[i] = i; } for(int i=n-1; i>=0; i--){ nxtl[a[i]] = fl(a[i] - 1); nxtr[a[i]] = fr(a[i] + 1); if(nxtr[a[i]] < n) rp[i] = i - r[nxtr[a[i]]]; if(nxtl[a[i]] >= 0) lp[i] = i - r[nxtl[a[i]]]; } int p = 0; for(int i=1; i<n; i++){ while(p > 0 && !ins1(i, p)){ p = fail[p]; } if(ins1(i, p)) p++; fail[i+1] = p; } p = 0; vector<int> v; for(int i=0; i<m; i++){ scanf("%d",&b[i]); while(p > 0 && !ins2(i, p)){ p = fail[p]; } if(ins2(i, p)) p++; if(p == n){ v.push_back(i - n + 2); p = fail[p]; } } printf("%d\n", v.size()); for(auto &i : v) printf("%d ",i); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 3 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 356 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 768 KB | Output is correct |
2 | Correct | 5 ms | 768 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 768 KB | Output is correct |
2 | Correct | 5 ms | 768 KB | Output is correct |
3 | Correct | 3 ms | 512 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 3804 KB | Output is correct |
2 | Correct | 25 ms | 2576 KB | Output is correct |
3 | Correct | 43 ms | 4728 KB | Output is correct |
4 | Correct | 46 ms | 4716 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 4700 KB | Output is correct |
2 | Correct | 35 ms | 3292 KB | Output is correct |
3 | Correct | 39 ms | 4088 KB | Output is correct |
4 | Correct | 41 ms | 4588 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 4724 KB | Output is correct |
2 | Correct | 34 ms | 4088 KB | Output is correct |
3 | Correct | 36 ms | 3764 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 240 ms | 21688 KB | Output is correct |
2 | Correct | 646 ms | 48092 KB | Output is correct |
3 | Correct | 126 ms | 11896 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 182 ms | 23252 KB | Output is correct |
2 | Correct | 135 ms | 11132 KB | Output is correct |
3 | Correct | 539 ms | 43512 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 157 ms | 14836 KB | Output is correct |
2 | Correct | 198 ms | 21760 KB | Output is correct |
3 | Correct | 173 ms | 16340 KB | Output is correct |
4 | Correct | 272 ms | 48820 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 156 ms | 16816 KB | Output is correct |
2 | Correct | 176 ms | 16524 KB | Output is correct |
3 | Correct | 74 ms | 9464 KB | Output is correct |
4 | Correct | 560 ms | 45068 KB | Output is correct |