답안 #585635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585635	2022-06-29T06:56:18 Z	amunduzbaev	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	140 ms	11708 KB

palindromic

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;


const int N = 1e4 + 5;
const int P = 167;
const int mod = 1e9 + 7;

void solve(){
	string s; cin >> s;
	int n = s.size();
	s = "#" + s;
	int h[n + 1] {}, pw[n + 1];
	pw[0] = 1;
	for(int i=1;i<=n;i++){
		h[i] = (h[i - 1] * 1ll * P + s[i] - 'a') % mod;
		pw[i] = pw[i - 1] * 1ll * P % mod;
	}
	
	auto check = [&](int l, int r){ l--;
		return (h[r] - h[l] * 1ll * pw[r - l] % mod + mod) % mod == 
		(h[n - l] - h[n - r] * 1ll * pw[r - l] % mod + mod) % mod;
	};
	
	int res = 0, last = 1;
	for(int i=1;i<=n/2;i++){
		if(check(last, i)){
			//~ cout<<last<<" "<<i<<"\n";
			res += 2;
			last = i + 1;
		}
	}
	
	if(n & 1) res++;
	else if(last <= n / 2) res++;
	
	cout<<res<<"\n";
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int t; cin>>t;
	while(t--){
		solve();
	}
}

Subtask #1

15.0 / 15.0

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

Subtask #2

20.0 / 20.0

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

Subtask #3

25.0 / 25.0

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

Subtask #4

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	324 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	2 ms	464 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	2 ms	460 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	140 ms	11708 KB	Output is correct
15	Correct	75 ms	11200 KB	Output is correct
16	Correct	139 ms	11312 KB	Output is correct
17	Correct	79 ms	6656 KB	Output is correct