oj.uz

답안 #13059

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13059 2015-01-28T14:04:54 Z ejnahc 백신 (KOI13_vaccine) C++
0 / 24
 38 ms 2296 KB 
#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;
}

Subtask #1
0.0 / 2.64

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 1768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.12

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 1768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 3.6

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 1768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 4.32

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.8

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 5.52

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 2296 KB Output isn't correct
2 Halted 0 ms 0 KB -