Submission #349302

#TimeUsernameProblemLanguageResultExecution timeMemory
349302silverfishMatching (CEOI11_mat)C++14
63 / 100
573 ms65540 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("Ofast,unroll-loops") using namespace std; /*<DEBUG>*/ #define tem template <typename #define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i) #define _op debug& operator<< tem C > auto test(C *x) -> decltype(cerr << *x, 0LL); tem C > char test(...); tem C > struct itr{C begin, end; }; tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; } struct debug{ #ifdef _LOCAL ~debug(){ cerr << endl; } tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; } tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); } tem T, typename U > _op (pair<T, U> i){ return *this << "< " << i.first << " , " << i.second << " >"; } tem T> _op (itr<T> i){ *this << "{ "; for(auto it = i.begin; it != i.end; it++){ *this << " , " + (it==i.begin?2:0) << *it; } return *this << " }"; } #else tem T> _op (const T&) { return *this; } #endif }; string _ARR_(int* arr, int sz){ string ret = "{ " + to_string(arr[0]); for(int i = 1; i < sz; i++) ret += " , " + to_string(arr[i]); ret += " }"; return ret; } #define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]" /*</DEBUG>*/ typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef pair<int, int> pii; //mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pb push_back #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define TC int __TC__; cin >> __TC__; while(__TC__--) #define ar array const int INF = 1e9 + 7, N = 1e6; int p[2*N+1], pi[2*N+1]; struct Node{ Node (){} int *data; Node *left, *right; }; Node *root; int n, m; //start of merge sort tree void build(int lx, int rx, Node *x){ x->data = new int[rx-lx+1]; if(lx == rx){ x->data[0] = p[lx]; return; } int m = lx + (rx - lx+1)/2; x->left = new Node; x->right = new Node; build(lx, m-1, x->left); build(m, rx, x->right); //merge merge(x->left->data, x->left->data + (m-1 -lx + 1), x->right->data, x->right->data + (rx - m + 1), x->data); return; } int get(int lx, int rx, Node* x, int l, int r, int v){ if(lx >= l && rx <= r){ return (lower_bound(x->data, x->data + (rx - lx + 1), v) - x->data); } if(r < lx || l > rx) return 0; int m = lx + (rx - lx+1) / 2; return get(lx, m-1, x->left, l, r, v) + get(m, rx, x->right, l, r, v); } int get(int l, int r){ if(l==r) return 0; return get(0, n+m, root, l, r-1, p[r]); } int main(void) { FAST; cin >> n >> m; for(int i = 0; i < n; ++i){ int x; cin >> x; p[--x] = i+1; } p[n] = -1; for(int i = n+1; i <= n+m; ++i){ cin >> p[i]; p[i] += n; } // build merge sort tree root = new Node; build(0, n+m, root); pi[0] = 0; int cnt = 0; vector<int> ans; for(int i = 1; i <= n+m; ++i){ int j = pi[i-1]; if(j == n) j = pi[j-1]; while(j > 0 && get(0, j) != get(i-j, i)){ j = pi[j-1]; } if(get(0,j) == get(i - j, i)) ++j; pi[i] = j; if(p[i] == -1) pi[i] = 0; if(pi[i] == n){ ++cnt; ans.pb(i-n-n); } } cout << cnt << '\n'; for(int i : ans) cout << i+1 << ' '; cout << '\n'; return 0; }
#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...