oj.uz

Submission #223553

# Submission time Handle Problem Language Result Execution time Memory
223553 2020-04-15T11:37:28 Z tqbfjotld Lampice (COCI19_lampice) C++14
25 / 110
 8 ms 1152 KB 
#include <bits/stdc++.h>
using namespace std;

string findLongestPalindromicString(string text) {
    int N = text.size();
    if(N == 0)
        return "";
    N = 2*N + 1; //Position count
    int L[N]; //LPS Length Array
    L[0] = 0;
    L[1] = 1;
    int C = 1; //centerPosition
    int R = 2; //centerRightPosition
    int i = 0; //currentRightPosition
    int iMirror; //currentLeftPosition
    int expand = -1;
    int diff = -1;
    int maxLPSLength = 0;
    int maxLPSCenterPosition = 0;
    int start = -1;
    int en = -1;

    //Uncomment it to print LPS Length array
    //printf("%d %d ", L[0], L[1]);
    for (i = 2; i < N; i++){
        //get currentLeftPosition iMirror for currentRightPosition i
        iMirror  = 2*C-i;
        //Reset expand - means no expansion required
        expand = 0;
        diff = R - i;
        //If currentRightPosition i is within centerRightPosition R
        if(diff >= 0){
            if(L[iMirror] < diff) // Case 1
                L[i] = L[iMirror];
            else if(L[iMirror] == diff && R == N-1) // Case 2
                L[i] = L[iMirror];
            else if(L[iMirror] == diff && R < N-1){
                    L[i] = L[iMirror];
                    expand = 1;  // expansion required
            }
            else if(L[iMirror] > diff){
                L[i] = diff;
                expand = 1;  // expansion required
            }
        }
        else{
            L[i] = 0;
            expand = 1;  // expansion required
        }

        if (expand == 1){
            //Attempt to expand palindrome centered at currentRightPosition i
            //Here for odd positions, we compare characters and
            //if match then increment LPS Length by ONE
            //If even position, we just increment LPS by ONE without
            //any character comparison
            while (((i+L[i])<N&&(i-L[i])>0)&&(((i+L[i]+1)%2==0)||(text[(i+L[i]+1)/2]==text[(i-L[i]-1)/2]))){
                L[i]++;
            }
        }

        if(L[i] > maxLPSLength){
            maxLPSLength = L[i];
            maxLPSCenterPosition = i;
        }

        // If palindrome centered at currentRightPosition i
        // expand beyond centerRightPosition R,
        // adjust centerPosition C based on expanded palindrome.
        if (i + L[i] > R){
            C = i;
            R = i + L[i];
        }
        //Uncomment it to print LPS Length array
        //printf("%d ", L[i]);
    }
    //printf("\n");
    start = (maxLPSCenterPosition - maxLPSLength)/2;
    en = start + maxLPSLength - 1;
    //printf("start: %d end: %d\n", start, end);
    return text.substr(start,en-start+1);
}

int main(){
   int n;
   cin>>n;
   string str;
   cin>>str;
   printf("%d",findLongestPalindromicString(str).size());
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:89:56: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::__cxx11::basic_string<char>::size_type {aka long unsigned int}' [-Wformat=]
    printf("%d",findLongestPalindromicString(str).size());
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 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 8 ms 896 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 8 ms 1024 KB Output is correct
5 Correct 8 ms 1152 KB Output is correct
6 Correct 8 ms 1152 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 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 384 KB Output isn't correct
2 Halted 0 ms 0 KB -