제출 #1126113

#제출 시각아이디문제언어결과실행 시간메모리
1126113Mike_VuMatching (CEOI11_mat)C++17
100 / 100
291 ms35592 KiB
///problem: https://oj.uz/problem/view/CEOI11_mat #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double dou; #define pii pair<int, int> #define fi first #define se second #define pb push_back #define ALL(v) v.begin(), v.end() #define BITJ(x, j) (((x)>>(j))&1) #define MASK(j) (1LL<<(j)) template<typename T> bool maximize(T &x, const T &y) { if (x < y) {x = y; return 1;} return 0; } template<typename T> bool minimize(T &x, const T &y) { if (x > y) {x = y; return 1;} return 0; } const int maxn = 1e6+5; int n, m, a[maxn], b[maxn]; int pleft[maxn], pright[maxn], ind[maxn]; //pointer left-right int posdown[maxn], posup[maxn]; //positions of comparing numbers int kmp[maxn], match[maxn]; vector<int> ans; void setupval() { for (int i = 1; i <= n ;i++) { ind[a[i]] = i; pleft[i] = i-1; pright[i] = i+1; } for (int i = n; i; i--) { posdown[i] = pleft[a[i]] != 0 ? ind[pleft[a[i]]] : -1; posup[i] = pright[a[i]] != n+1 ? ind[pright[a[i]]] : -1; //del pright[pleft[a[i]]] = pright[a[i]]; pleft[pright[a[i]]] = pleft[a[i]]; } // for (int i = 1; i <= n; i++) { // cout << i << ' ' << posdown[i] << ' ' << posup[i] << "\n"; // } } bool check(int len, int i, int val[]) {///check if i is the len element if (posdown[len] != -1) { if (val[i-(len-posdown[len])] >= val[i]) return 0; } if (posup[len] != -1) { if (val[i-(len-posup[len])] <= val[i]) return 0; } return 1; } void setupkmp() { int temp = kmp[1] = 0; for (int i = 2; i <= n; i++) { while (temp > 0 && !check(temp+1, i, a)) temp = kmp[temp]; kmp[i] = check(temp+1, i, a) ? ++temp : 0; } // for (int i = 1; i <= n; i++) { // cout << kmp[i] << ' '; // } // cout << "\n"; } void solvekmp() { int temp = match[0] = 0; for (int i = 1; i <= m; i++) { if (temp == n) temp = kmp[temp]; while (temp > 0 && !check(temp+1, i, b)) temp = kmp[temp]; match[i] = check(temp+1, i, b) ? ++temp : 0; if (match[i] == n) { ans.pb(i-n+1); } } // for (int i= 1; i <= m; i++) { // cout << match[i] << ' '; // } // cout << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // #define name "task" // if (fopen(name".inp", "r")){ // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); // } cin >> n >> m; for (int i= 1; i <= n; i++) { int x; cin >> x; a[x] = i; } for (int j = 1; j <= m; j++) { cin >> b[j]; } setupval(); setupkmp(); solvekmp(); cout << (int)ans.size() << "\n"; for (int x : ans) { cout << x << ' '; } }
#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...