Submission #172207

#	Time	Username	Problem	Language	Result	Execution time	Memory
172207		nicolaalexandra	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	569 ms	11188 KiB

palindromic

#include <bits/stdc++.h>
#define DIM 1000010
#define MOD 1000000007
using namespace std;
int t,n,i,j;
char v[DIM];
vector <int> poz[30];

int main (){
    //ifstream fin ("date.in");
    //ofstream fout ("date.out");
    cin>>t;
    for (;t--;){

        cin>>v+1;
        n = strlen (v+1);
        //for (i=1;i<=n;i++)
            // hash[i] = (hash[i-1]*27 + v[i]-'a')%MOD;
        int st = 1, dr = n, sol = 0;
        int st_ant = 0, dr_ant = n+1, nr = 0;
        long long prf = 0, suf = 0, p = 1;
        while (st < dr){

            prf = (prf*27 + v[st] - '0')%MOD;
            suf = (suf + p*(v[dr] - '0'))%MOD;
            p = (p*27)%MOD;
            nr++;
            if (prf == suf){
                /// trb sa mai testez odata daca sunt egale
                int ok = 1;
                for (int i=st_ant+1,j=dr;i<=st,j<dr_ant;i++,j++){
                    if (v[i] != v[j]){
                        ok = 0;
                        break;
                    }}
                if (ok){ /// sunt egale
                    sol += 2;
                    prf = 0, suf = 0, p = 1, nr = 0;
                    st_ant = st, dr_ant = dr;
                }
            }
            st++, dr--;
        }
        if (st == dr || nr)
            sol++;

        cout<<sol<<"\n";

    }



    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:15:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin>>v+1;
              ~^~
palindromic.cpp:31:43: warning: left operand of comma operator has no effect [-Wunused-value]
                 for (int i=st_ant+1,j=dr;i<=st,j<dr_ant;i++,j++){
                                          ~^~~~

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40