oj.uz

Submission #916710

# Submission time Handle Problem Language Result Execution time Memory
916710 2024-01-26T10:28:30 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 9 ms 1368 KB 
#include <bits/stdc++.h>

using namespace std;

unsigned int longpal_partitions(char *word)
{
    const unsigned int n=strlen(word);
    const unsigned int prime=131;

    unsigned int countedch=0;
    unsigned int piececounts=0;

    while(countedch*2<n)
    {
        unsigned int lhash=0,rhash=0,power=1;

        for(unsigned int piecesize=1;true;piecesize++)
        {
            unsigned int l=countedch,r=n-countedch-piecesize;
            if(l+piecesize-1>=r)
                return piececounts+1;
            if(piecesize==1)
                power=1;
            else
                power*=prime;
            lhash+=static_cast<unsigned int>(word[l+piecesize-1])*power;
            rhash=static_cast<unsigned int>(word[r])+rhash*prime;
            if(lhash==rhash && strncmp(word+l,word+r,piecesize)==0)
            {
                piececounts+=2;
                countedch+=piecesize;
                break;
            }
        }
    }
    return piececounts;
}

int main()
{
    unsigned int n;
    char word[510000];
    cin>>n;
    for(unsigned int i=0;i<n;i++)
    {
        cin>>word;
        assert(strlen(word)<=510000);
        cout<<longpal_partitions(word)<<endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 864 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 864 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 864 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 864 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Runtime error 9 ms 1368 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -