제출 #1170301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170301		DangKhoizzzz	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	125 ms	19424 KiB

palindromic

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

/*
+ array limit ???
+ special case ??? n = 1?
+ time limit ???
*/

using namespace std;

const int mod = 1e9 + 7;
const int base = 37;
const int INF = 1e18 + 7;
const int maxn = 1e6 + 7;

int n , prehash[maxn] , prepow[maxn];
string s;

void build_hash()
{
    prepow[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        prepow[i] = (prepow[i-1] * base)%mod;
    }
    for(int i = 1; i <= n; i++)
    {
        prehash[i] = (prehash[i-1]*base + (s[i] - 'a'))%mod;
    }
}

int gethash(int l , int r)
{
    return (prehash[r] - prehash[l-1]*prepow[r - l + 1] + mod*mod)%mod;
}

void solve()
{
    cin >> s;
    n = s.size();
    s = '@' + s;
    build_hash();

    int l1 = 1 , r1 = 1;
    int l2 = n , r2 = n;

    int ans = 0;
    int remain = n;

    while(r1 <= n/2)
    {
        while(r1 <= n/2)
        {
            if(gethash(l1 , r1) == gethash(l2 , r2))
            {
                ans += 2;
                remain -= (r1 - l1 + 1)*2;
                break;
            }
            r1++;
            l2--;
        }
        r1++;
        l1 = r1;
        l2--;
        r2 = l2;
    }
    cout << ans + (remain > 0) << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--)solve();
    return 0;
}

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