Submission #13059

#TimeUsernameProblemLanguageResultExecution timeMemory
13059ejnahc백신 (KOI13_vaccine)C++98
0 / 24
38 ms2296 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; int N,K; vector<int> getPartialMatch(const vector<int>& N) { int m = N.size(); vector<int> pi(m, 0); int begin = 1, matched = 0; while (begin + matched < m) { if (N[begin+matched] == N[matched]) { ++matched; pi[begin+matched-1] = matched; } else { if (matched == 0) ++begin; else { begin += matched - pi[matched-1]; matched = pi[matched-1]; } } } return pi; } bool kmpSearch(const vector<int>& H, const vector<int>& N) { int n = H.size(), m = N.size(); vector<int> pi = getPartialMatch(N); for (int jump=0; jump<=n-K; jump+=K) { int begin = 0, matched = 0, begin2 = 0; while (begin <= n - K) { if (matched < m && H[begin + matched] == N[matched+jump]) { ++matched; if (matched >= K) return true; } else { if (matched == 0) ++begin; else { begin += matched - pi[matched-1]; matched = pi[matched-1]; } } } } return false; } vector<int> codes[1001]; vector<int> codesR[1001]; int main() { cin >> N >> K; for (int i=0; i<N; ++i) { int n; cin >> n; for (int j=0; j<n; ++j) { int num; cin >> num; codes[i].push_back(num); codesR[i].push_back(num); } reverse(codesR[i].begin(), codesR[i].end()); } int s = 0; for (int i=0; i<N; ++i) { for (int j=0; j<N; ++j) { if (i == j) continue; if (kmpSearch(codes[i], codes[j]) || kmpSearch(codes[i], codesR[j])) { s++; } if (s == K) { cout << "YES"; return 0; } } } cout << "NO"; 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...