oj.uz

Submission #916750

# Submission time Handle Problem Language Result Execution time Memory
916750 2024-01-26T13:04:05 Z yellowtoad Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 215 ms 28224 KB 
#include <iostream>
#include <vector>
using namespace std;

const long long mod = (1LL<<41)-1;
long long test, a[1000010], st, ed, r, lst, pos, sum, ans;
string s, t;
vector<string> v;

int main() {
	cin >> test;
	a[0] = 1;
	for (int i = 1; i <= 1e6; i++) a[i] = (a[i-1]*26)%mod;
	while (test--) {
		cin >> s;
		st = ed = sum = ans = pos = 0;
		r = lst = s.length()-1;
		v.clear();
		t = "";
		for (int i = 0; i < s.length(); i++) {
			if (i >= r) {
				pos = i;
				break;
			}
			st = (st*26+s[i]-'A')%mod;
			(ed += (a[lst-r]*(s[r]-'A'))) %= mod;
			t += s[i];
			if (st == ed) {
				v.push_back(t);
				sum += t.length();
				t = "";
				lst = r-1;
				st = ed = 0;
			}
			r--;
		}
		for (int i = 0; i < v.size(); i++) ans++;
		if (sum*2 != s.length()) ans++;
		for (int i = v.size()-1; i >= 0; i--) ans++;
		cout << ans << endl;
	}
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:20:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for (int i = 0; i < s.length(); i++) {
      |                   ~~^~~~~~~~~~~~
palindromic.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int i = 0; i < v.size(); i++) ans++;
      |                   ~~^~~~~~~~~~
palindromic.cpp:38:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   if (sum*2 != s.length()) ans++;
      |       ~~~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8024 KB Output is correct
2 Correct 7 ms 8028 KB Output is correct
3 Correct 7 ms 8040 KB Output is correct
4 Correct 7 ms 8024 KB Output is correct
5 Correct 7 ms 8024 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8024 KB Output is correct
2 Correct 7 ms 8028 KB Output is correct
3 Correct 7 ms 8040 KB Output is correct
4 Correct 7 ms 8024 KB Output is correct
5 Correct 7 ms 8024 KB Output is correct
6 Correct 7 ms 8028 KB Output is correct
7 Correct 6 ms 8044 KB Output is correct
8 Correct 6 ms 8024 KB Output is correct
9 Correct 6 ms 8028 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8024 KB Output is correct
2 Correct 7 ms 8028 KB Output is correct
3 Correct 7 ms 8040 KB Output is correct
4 Correct 7 ms 8024 KB Output is correct
5 Correct 7 ms 8024 KB Output is correct
6 Correct 7 ms 8028 KB Output is correct
7 Correct 6 ms 8044 KB Output is correct
8 Correct 6 ms 8024 KB Output is correct
9 Correct 6 ms 8028 KB Output is correct
10 Correct 8 ms 8792 KB Output is correct
11 Correct 8 ms 8280 KB Output is correct
12 Correct 9 ms 8280 KB Output is correct
13 Correct 9 ms 8412 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8024 KB Output is correct
2 Correct 7 ms 8028 KB Output is correct
3 Correct 7 ms 8040 KB Output is correct
4 Correct 7 ms 8024 KB Output is correct
5 Correct 7 ms 8024 KB Output is correct
6 Correct 7 ms 8028 KB Output is correct
7 Correct 6 ms 8044 KB Output is correct
8 Correct 6 ms 8024 KB Output is correct
9 Correct 6 ms 8028 KB Output is correct
10 Correct 8 ms 8792 KB Output is correct
11 Correct 8 ms 8280 KB Output is correct
12 Correct 9 ms 8280 KB Output is correct
13 Correct 9 ms 8412 KB Output is correct
14 Correct 215 ms 26932 KB Output is correct
15 Correct 107 ms 28224 KB Output is correct
16 Correct 169 ms 18864 KB Output is correct
17 Correct 130 ms 18500 KB Output is correct