제출 #1128554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128554		PagodePaiva	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	1105 ms	50188 KiB

palindromic

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fr first
#define sc second

using namespace std;

const int N = 1000010;
const int p = 1e9+7;
const int q = 1e9+9;
const int b = 127;
int pot[N][2];
int potinv[N][2];

int binpow(int a, int b, int mod){
    if(b == 0) return 1;
    int t = binpow(a, b/2, mod);
    t *= t;
    t %= mod;
    if(b%2 == 0) return t;
    else return (a*t)%mod;
}

struct hs{
    pair <int, int> pref[N];
    void build(string s){
        pref[0] = {0, 0};
        for(int i = 0;i < s.size();i++){
            pref[i+1].fr = (pref[i].fr + ((s[i]-'a'+1)*pot[i][0])%p)%p;
            pref[i+1].sc = (pref[i].sc+((s[i]-'a'+1)*pot[i][1])%q)%q;
        }
    }
    pair <int, int> query(int l, int r){
        l++;
        r++;
        return {(((pref[r].first+p-pref[l-1].first)%p)*potinv[l-1][0])%p, (((pref[r].second+q-pref[l-1].second)%q)*potinv[l-1][1])%q};
    }
    bool get(int l1, int r1, int l2, int r2){
        if(query(l1, r1) == query(l2, r2)) return true;
        return false;
    }
} h;

void solve(){
	string s;
	cin >> s;
	int res = 0;
	int l = 0, r = s.size();
	r--;
	int a = 0, b = r;
	h.build(s);
	while(l < r){
		if(h.query(a, l) == h.query(r, b)){
			a = l+1;
			b = r-1;
			res += 2;
		}
		l++;
		r--;
	}
	if(a == l and l != r){
		cout << res << endl;
	}
	else cout << res+1 << endl;
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int t;
	cin >> t;
	pot[0][0] = pot[0][1] = 1;
    potinv[0][0] = potinv[0][1] = 1;
    for(int i = 1;i < N;i++){
        pot[i][0] = (pot[i-1][0]*b)%p;
        pot[i][1] = (pot[i-1][1]*b)%q;
        potinv[i][0] = binpow(pot[i][0], p-2, p);
        potinv[i][1] = binpow(pot[i][1], q-2, q);
    }
	while(t--){
		solve();
	}
}

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