제출 #501201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501201		radal	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	63 ms	16692 KiB

palindromic

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
const long long int N = 1e6+20,mod = 1e9+7,inf = 1e9+10,sq = 400;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,int k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
int pw[N];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int T;
    cin >> T;
    pw[0] = 1;
    rep(i,1,N) pw[i] = 1ll*307*pw[i-1]%mod;
    while (T--){
        int n;
        string s;
        cin >> s;
        n = s.size();
        if (n == 1){
            cout << 1 << endl;
            continue;
        }
        int ans = 0,h = 0,g = 0,l = 0, r = n-1;
        int t = 0;
        while (r > l){
            h = mkay((s[l]-'a'+1),1ll*h*307%mod);
            g = mkay(g,1ll*(s[r]-'a'+1)*pw[t]%mod);
            t++;
            r--;
            l++;
            if (h == g){
                ans += 2;
                if (l == r) ans++;
                t = 0;
                h = 0;
                g = 0;
                continue;
            }
            if (r <= l){
                ans++;
                break;
            }
        }
        cout << ans << endl;
    }
}

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