oj.uz

답안 #115345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115345 2019-06-06T18:11:35 Z model_code Matching (CEOI11_mat) C++17
100 / 100
 785 ms 31736 KB 
/*
 * Task: Matching
 *  Model solution
 *  O(n + m)
 * Author: Jakub Lacki
 */

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

#define FOR(I,A,B) for(int I=(A);I<=(B);I++)
#define FORD(I,A,B) for(int I=(A);I>=(B);I--)
#define REP(I,N) for(int I=0;I<(N);I++)
#define ALL(X) (X).begin(),(X).end()
#define PB push_back
#define MP make_pair
#define VAR(V,init) __typeof(init) V=(init)
#define FORE(I,C) for(VAR(I,(C).begin());I!=(C).end();I++)

void bigger_and_smaller(const vector<int>& tab, vector<int>* bigger, vector<int>* smaller)
{
    int n = tab.size();
    vector<int> next(n), prev(n), where_is(n);
    
    bigger->resize(n);
    smaller->resize(n);

    for(int i=0; i<n; i++)
    {
        next[i] = i+1;
        prev[i] = i-1;
        where_is[tab[i]] = i;
    }

    for(int i=n-1; i>=0; i--)
    {
        int x = tab[i];
        if(next[x] == n)
            (*bigger)[i] = -1;
        else
            (*bigger)[i] = where_is[next[x]];
        if(prev[tab[i]] == -1)
            (*smaller)[i] = -1;
        else
            (*smaller)[i] = where_is[prev[x]];
        if(prev[x] != -1)
            next[prev[x]] = next[x];
        if(next[x] != n)
            prev[next[x]] = prev[x];
    }
}

bool kmp_equal(const vector<int>& text, int a, int b, const vector<int>& bigger, const vector<int>& smaller)
{
    if(bigger[a] != -1 && text[b] > text[b-(a - bigger[a])])
        return false;
    if(smaller[a] != -1 && text[b] < text[b-(a - smaller[a])])
        return false;
    return true;
}

vector<int> kmp(const vector<int>& pattern, const vector<int>& text)
{
    int n = pattern.size();
    vector<int> p(n);
    vector<int> ret, bigger, smaller;

    bigger_and_smaller(pattern, &bigger, &smaller);
    p[0] = 0;
    
    for(int i=1; i<n; i++)
    {
        int j = p[i-1];
        while(j && !kmp_equal(pattern, j, i, bigger, smaller)) j = p[j-1];
        if(kmp_equal(pattern, j, i, bigger, smaller))
            j ++;
        p[i] = j;
    }

    int matched_characters = 0;
    for(size_t i=0; i<text.size(); i++)
    {
        while(matched_characters && !kmp_equal(text, matched_characters, i, bigger, smaller))
            matched_characters = p[matched_characters-1];
        if(kmp_equal(text, matched_characters, i, bigger, smaller))
            matched_characters ++;

        if(matched_characters == n)
        {
            ret.push_back(i - n + 1);
            matched_characters = p[matched_characters-1];
        }
    }
    
    return ret;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> pattern(n), text(m);
    
    for(int i=0; i<n; i++)
    {
        int x;
        scanf("%d",&x);
        pattern[x-1] = i;
    }
    
    for(int i=0; i<m; i++)
        scanf("%d", &text[i]);
    
    vector<int> matches = kmp(pattern, text);
    printf("%d\n", matches.size());
    for(size_t i=0; i<matches.size(); i++)
    {
        printf("%d", matches[i]+1);
        if(i+1 < matches.size())
            printf(" ");
    }
    printf("\n");
    return 0;
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:118:34: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", matches.size());
                    ~~~~~~~~~~~~~~^
mat.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
mat.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
mat.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &text[i]);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 484 KB Output is correct
3 Correct 3 ms 256 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 2140 KB Output is correct
2 Correct 25 ms 1272 KB Output is correct
3 Correct 45 ms 2524 KB Output is correct
4 Correct 47 ms 2424 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 2424 KB Output is correct
2 Correct 35 ms 1272 KB Output is correct
3 Correct 40 ms 1912 KB Output is correct
4 Correct 46 ms 3336 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 2424 KB Output is correct
2 Correct 36 ms 2296 KB Output is correct
3 Correct 43 ms 1784 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 10696 KB Output is correct
2 Correct 785 ms 31708 KB Output is correct
3 Correct 129 ms 4136 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 12664 KB Output is correct
2 Correct 146 ms 4224 KB Output is correct
3 Correct 624 ms 30456 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 5804 KB Output is correct
2 Correct 223 ms 15048 KB Output is correct
3 Correct 173 ms 6268 KB Output is correct
4 Correct 277 ms 31736 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 6904 KB Output is correct
2 Correct 170 ms 6088 KB Output is correct
3 Correct 77 ms 5012 KB Output is correct
4 Correct 301 ms 28924 KB Output is correct