oj.uz

Submission #366684

# Submission time Handle Problem Language Result Execution time Memory
366684 2021-02-15T00:26:03 Z penguinhacker Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 448 ms 36104 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int MOD = 1e9 + 7;

namespace Hashing {

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> BDIST(0.1 * MOD, 0.9 * MOD);
const ar<int, 2> base = {BDIST(rng), BDIST(rng)};

ar<int, 2> operator+ (ar<int, 2> a, ar<int, 2> b) {
	for (int i = 0; i < 2; ++i)
		if ((a[i] += b[i]) >= MOD)
			a[i] -= MOD;
	return a;
}
ar<int, 2> operator- (ar<int, 2> a, ar<int, 2> b) {
	for (int i = 0; i < 2; ++i)
		if ((a[i] -= b[i]) < 0)
			a[i] += MOD;
	return a;
}
ar<int, 2> operator* (ar<int, 2> a, ar<int, 2> b) {
	for (int i = 0; i < 2; ++i)
		a[i] = (ll)a[i] * b[i] % MOD;
	return a;
}
ar<int, 2> make_hash(char c) {
	return {c, c};
}

vector<ar<int, 2>> pows = {{1, 1}};
void extend(int len) {
	while(pows.size() <= len)
		pows.push_back(base * pows.back());
}

struct hstring {
	string s;
	vector<ar<int, 2>> pre = {{0, 0}};
	void add(string t) {
		s += t;
		for (char c : t)
			pre.push_back(base * pre.back() + make_hash(c));
	}
	ar<int, 2> hash(int l, int r) {
		assert(0 <= l && l <= r && r < s.size());
		int len = r - l + 1;
		extend(len);
		return pre[r + 1] - pows[len] * pre[l];
	}
};

}
using namespace Hashing;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t; cin >> t;
	while(t--) {
		string s; cin >> s;
		int n = s.size();
		hstring hs; hs.add(s);
		int last = 0;
		int ans = 0;
		for (int i = 0; i < n / 2; ++i) {
			if (hs.hash(last, i) == hs.hash(n - i - 1, n - last - 1)) {
				last = i + 1;
				ans += 2;
			}
		}
		ans += 2 * last < n;
		cout << ans << "\n";
	}
	return 0;
}

Compilation message

palindromic.cpp: In function 'void Hashing::extend(int)':
palindromic.cpp:38:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |  while(pows.size() <= len)
      |        ~~~~~~~~~~~~^~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from palindromic.cpp:1:
palindromic.cpp: In member function 'std::array<int, 2> Hashing::hstring::hash(int, int)':
palindromic.cpp:51:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   assert(0 <= l && l <= r && r < s.size());
      |                              ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 5 ms 720 KB Output is correct
11 Correct 4 ms 668 KB Output is correct
12 Correct 5 ms 732 KB Output is correct
13 Correct 4 ms 704 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 5 ms 720 KB Output is correct
11 Correct 4 ms 668 KB Output is correct
12 Correct 5 ms 732 KB Output is correct
13 Correct 4 ms 704 KB Output is correct
14 Correct 416 ms 36104 KB Output is correct
15 Correct 233 ms 29088 KB Output is correct
16 Correct 448 ms 28176 KB Output is correct
17 Correct 261 ms 19688 KB Output is correct