oj.uz

Submission #129976

# Submission time Handle Problem Language Result Execution time Memory
129976 2019-07-13T16:55:55 Z TadijaSebez Palindromic Partitions (CEOI17_palindromic) C++11
100 / 100
 244 ms 22812 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
const int mod=998244353;
const int N=1000050;
int hs[N],po[N],ip[N];
int pow(int x, int k)
{
    int ret=1;
    for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;
    return ret;
}
void preprocess()
{
    int i;
    po[0]=1;
    for(i=1;i<N;i++) po[i]=(ll)po[i-1]*26%mod;
    int mul=pow(26,mod-2);
    ip[0]=1;
    for(i=1;i<N;i++) ip[i]=(ll)ip[i-1]*mul%mod;
}
char s[N];
void Build(int n)
{
    int i;
    for(i=1;i<=n;i++)
    {
        hs[i]=(ll)hs[i-1]*26%mod+(s[i]-'a'+1);
        hs[i]%=mod;
    }
}
int GetHash(int l, int r)
{
    int ret=hs[r]-(ll)hs[l-1]*po[r-l+1]%mod;
    if(ret<0) ret+=mod;
    return ret;
}
bool Compare(int l1, int r1, int l2, int r2)
{
    return GetHash(l1,r1)==GetHash(l2,r2);
}
int main()
{
    preprocess();
    int t;
    scanf("%i",&t);
    while(t--)
    {
        scanf("%s",s+1);
        int n=strlen(s+1);
        Build(n);
        int sol=0,i,j=1;
        for(i=1;i<=n-j+1;i++)
        {
            if(Compare(j,i,n-i+1,n-j+1))
            {
                sol++;
                if(i!=n-j+1) sol++;
                //printf("%i %i\n",j,i);
                j=i+1;
            }
        }
        printf("%i\n",sol);
        for(i=1;i<=n;i++) s[i]=0;
    }
    return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&t);
     ~~~~~^~~~~~~~~
palindromic.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",s+1);
         ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8184 KB Output is correct
2 Correct 20 ms 8184 KB Output is correct
3 Correct 20 ms 8184 KB Output is correct
4 Correct 20 ms 8184 KB Output is correct
5 Correct 20 ms 8188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8184 KB Output is correct
2 Correct 20 ms 8184 KB Output is correct
3 Correct 20 ms 8184 KB Output is correct
4 Correct 20 ms 8184 KB Output is correct
5 Correct 20 ms 8188 KB Output is correct
6 Correct 20 ms 8184 KB Output is correct
7 Correct 20 ms 8184 KB Output is correct
8 Correct 22 ms 8184 KB Output is correct
9 Correct 20 ms 8184 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8184 KB Output is correct
2 Correct 20 ms 8184 KB Output is correct
3 Correct 20 ms 8184 KB Output is correct
4 Correct 20 ms 8184 KB Output is correct
5 Correct 20 ms 8188 KB Output is correct
6 Correct 20 ms 8184 KB Output is correct
7 Correct 20 ms 8184 KB Output is correct
8 Correct 22 ms 8184 KB Output is correct
9 Correct 20 ms 8184 KB Output is correct
10 Correct 22 ms 8312 KB Output is correct
11 Correct 21 ms 8184 KB Output is correct
12 Correct 23 ms 8316 KB Output is correct
13 Correct 22 ms 8200 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8184 KB Output is correct
2 Correct 20 ms 8184 KB Output is correct
3 Correct 20 ms 8184 KB Output is correct
4 Correct 20 ms 8184 KB Output is correct
5 Correct 20 ms 8188 KB Output is correct
6 Correct 20 ms 8184 KB Output is correct
7 Correct 20 ms 8184 KB Output is correct
8 Correct 22 ms 8184 KB Output is correct
9 Correct 20 ms 8184 KB Output is correct
10 Correct 22 ms 8312 KB Output is correct
11 Correct 21 ms 8184 KB Output is correct
12 Correct 23 ms 8316 KB Output is correct
13 Correct 22 ms 8200 KB Output is correct
14 Correct 244 ms 22812 KB Output is correct
15 Correct 144 ms 18252 KB Output is correct
16 Correct 236 ms 22260 KB Output is correct
17 Correct 138 ms 15892 KB Output is correct