Submission #447384

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
447384	2021-07-26T08:26:44 Z	fuad27	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	80 ms	11796 KB

palindromic

#include<iostream>
using namespace std;
#define int long long
#define mod (long long)(1e17-3)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
int32_t main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);	
	int t;
	cin >> t;
	while(t--) {
		string s;
		cin >> s;
		int ans = 0, n = s.length();
		long long hash1 = 0, hash2 = 0, pw = 1, cnt = 0, j = n;
		for(int i = 0;i<n/2;i++) {
			hash1 = (26*hash1%mod + (s[i] - 'a'))%mod;
			hash2 = (hash2+((s[n-i-1]-'a'))*pw%mod)%mod;
			if(hash1 == hash2){
				hash1 = 0;
				hash2 = 0;
				ans+=2;
				pw = 1;
				j = i;
			}
			else pw=26*pw%mod;
		}
		if(j!=(n/2)-1 or n%2)ans++;
		cout<<ans<<'\n';
	}
}

Compilation message

palindromic.cpp: In function 'int32_t main()':
palindromic.cpp:17:43: warning: unused variable 'cnt' [-Wunused-variable]
   17 |   long long hash1 = 0, hash2 = 0, pw = 1, cnt = 0, j = n;
      |                                           ^~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	80 ms	11124 KB	Output is correct
15	Correct	43 ms	7668 KB	Output is correct
16	Correct	74 ms	11796 KB	Output is correct
17	Correct	44 ms	6924 KB	Output is correct