oj.uz

Submission #224002

# Submission time Handle Problem Language Result Execution time Memory
224002 2020-04-17T02:29:30 Z cheeheng Lampice (COCI19_lampice) C++14
25 / 110
 6 ms 1024 KB 
#include <bits/stdc++.h>
using namespace std;

char str[50005];
char S[50005];
int P[100005];
int L[100005]; // length of the palindrome for each center point in S (initially all 0s)

int main(){
    int N;
    scanf("%d", &N);

    scanf(" %s", str);

    // https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-4/
    // https://en.wikipedia.org/wiki/Longest_palindromic_substring

    S[0] = '|';
    memset(P, 0, sizeof(P));
    for(int i = 0; i < N; i ++){
        S[i*2+1] = str[i];
        S[i*2+2] = '|';
    }

    int c = 0, r = 0; // first element in S ('|') has been processed
    int m = 0, n = 0; // walking indices to check whether 2 elements are the same
    for(int i = 0; i <= 2*N; i ++){
        if(i > r){
            P[i] = 0;
            m = i-1;
            n = i+1;
        }else{
            int i2 = c*2-i; // left boundary
            if(P[i2] < r-i-1){
                P[i] = P[i2];
                m = -1; // bypass the while loop because one of the cases has been met
            }else{
                P[i] = r-i;
                n = r+1; // right boundary to check
                m = i*2-n; // left boundary to check
            }
        }
        while(m >= 0 && n < 2*N+1 && S[m] == S[n]){
            P[i] ++;
            m --; // adjust left boundary by 1
            n ++; // adjust right boundary by 1
        }

        if(i+P[i] > r){
            c = i;
            r = i+P[i];
        }
    }

    int ans = 0;
    for(int i = 0; i <= 2*N; i ++){
        ans = max(ans, P[i]);
    }

    printf("%d", ans);
    return 0;
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
lampice.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", str);
     ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 6 ms 896 KB Output is correct
3 Correct 6 ms 1024 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -