oj.uz

Submission #99932

# Submission time Handle Problem Language Result Execution time Memory
99932 2019-03-08T19:36:16 Z pavel Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 10 ms 4224 KB 
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;

const int MAXN = 1000006;
const int MOD = 1000000007;
const int BASE = 34;

int n;
char str[MAXN];
int p[MAXN];

int ADD(ll a, ll b){
    return (a+b)%MOD;
}

int MUL(ll a, ll b){
    return a*b%MOD;
}

int main(){
    p[0]=1;
    for(int i=1;i<MAXN;++i) p[i]=MUL(BASE, p[i-1]);
    int tcc;
    scanf("%d", &tcc);
    for(int tc=0;tc<tcc;++tc){
        scanf("%s", str);
        n=strlen(str);
        int ls=0,rs=n-1, le=1, re=n;
        int lh=str[0]-'a'+1, rh=str[n-1]-'a'+1;
        int sol=0;
        while(ls<rs){
            while(lh!=rh){
                lh=ADD(MUL(lh, BASE), str[le]-'a'+1);
                ++le;
                --rs;
                rh=ADD(MUL(str[rs]-'a'+1, p[re-rs-1]), rh);
            }
            if(ls==rs && le==re){
                sol++;
                break;
            }else{
                sol+=2;
            }
            ls=le;le=ls+1;lh=str[ls]-'a'+1;
            re=rs;rs=re-1;rh=str[rs]-'a'+1;
        }
        printf("%d\n", sol);
    }
}

Compilation message

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

Subtask #1
0 / 15.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

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