답안 #751567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751567	2023-05-31T18:53:24 Z	Fidan	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	157 ms	18132 KB

palindromic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=ll(a); i<ll(b); i++)
#define repn(i, a, b) for(ll i=ll(b)-1; i>=ll(a); i--)
#define be begin()
#define en end()
#define ff first
#define ss second
#define si size()
const ll mod=(1e9)+9;
void solve(){
	string s;
	cin>>s;
	ll n=s.si;
	ll l=0, h=n-1;
	ll s1=0, s2=0;
	ll sum=0;
	map<char, ll> mp;
	rep(i, 0, 26){
		mp[97+i]=i;
	}
	vector<ll> pw(n+10, 1);
	rep(i, 1, n+10){
		pw[i]=(pw[i-1]*26)%mod;
	}
	ll x=0;
	while(l<h){
		s1=(s1*26)%mod;
		s1=(s1+s[l])%mod;
		s2=(s2+(pw[x]*s[h])%mod)%mod;
		if(s1==s2){
			x=-1;
			sum+=2;
			s1=0, s2=0;
		}
		x++;
		l++, h--;
	}
	if(s1>0 || s2>0) sum++;
	else if(l==h) sum++;
	cout<<sum<<'\n';
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Subtask #1

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	324 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	324 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	2 ms	452 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct

Subtask #4

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	324 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	2 ms	452 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct
14	Correct	157 ms	17576 KB	Output is correct
15	Correct	90 ms	15768 KB	Output is correct
16	Correct	156 ms	18132 KB	Output is correct
17	Correct	89 ms	11108 KB	Output is correct