제출 #916011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916011		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	169 ms	20076 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int main()
{
    int t, p = 47;
    cin>>t;
    vector<ll> pw(1000001);
    pw[0] = 1;
    for (int i = 1; i <= 1000001; i++){
        pw[i] = (pw[i - 1] * p) % mod;
    }
    for (int it = 0; it < t; it++){
        string s;
        cin>>s;
        int l = 0, lind = -1, r = s.size() - 1;
        ll lhash = 0, rhash = 0, c = 0;
        while (l < r){
            lind++;
            lhash += s[l] * pw[lind];
            lhash %= mod;
            rhash = rhash * p + s[r];
            rhash %= mod;
            if (lhash == rhash){
                c += 2;
                lhash = 0;
                rhash = 0;
                lind = -1;
            }
            l++;
            r--;
        }
        if (l == r || lhash != 0 || rhash != 0){
            c++;
        }
        cout<<c<<"\n";
    }
}

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