답안 #941221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
941221	2024-03-08T09:46:56 Z	viwlesxq	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	53 ms	12800 KB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
	return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
	return a < b ? (a = b) == b : false;
}

const int p = 31;
const int m = 1e9 + 9;

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t; cin >> t;
	while (t--) {
		string s; cin >> s;
		int l = 0, r = size(s) - 1;
		int res = 0;
		while (l < r) {
			int l_hash = s[l++] - 'a' + 1, r_hash = s[r--] - 'a' + 1, p_pow = p;
			while (l < r && l_hash != r_hash) {
				l_hash = (l_hash + (s[l] - 'a' + 1) * p_pow % m) % m;
				r_hash = r_hash * p % m;
				r_hash = (r_hash + s[r] - 'a' + 1) % m;
				l++, r--;
				p_pow = p_pow * p % m;
			}
			if (l_hash == r_hash) res += 2;
			else if (l != r) res++;
		}
		if (l == r) res++;
		cout << res << '\n';
	}
}

Subtask #1

15.0 / 15.0

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

Subtask #2

20.0 / 20.0

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

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	456 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct

Subtask #4

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	456 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	43 ms	12800 KB	Output is correct
15	Correct	27 ms	7792 KB	Output is correct
16	Correct	53 ms	11984 KB	Output is correct
17	Correct	20 ms	7064 KB	Output is correct