Submission #224002

#	Time	Username	Problem	Language	Result	Execution time	Memory
224002		cheeheng	Lampice (COCI19_lampice)	C++14	25 / 110	6 ms	1024 KiB

lampice

#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 (stderr)

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
• Subtask 2: 25 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37