Submission #1303513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303513		thuhienne	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	80 ms	19500 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define thuhien ""
#define re exit(0);

#define hash __hash__

const int maxn = 1000009;
const ll mod = 1e9 + 7,base = 31;

string s;
int n;
ll hash[maxn],power[maxn];

void createhash() {
	power[0] = 1;
	for (int i = 1;i <= n;i++) {
		hash[i] = (hash[i - 1] * base + s[i] - 'a' + 1) % mod;
		power[i] = power[i - 1] * base % mod;
	}
}
int gethash(int l,int r) {
	return (hash[r] - hash[l - 1] * power[r - l + 1] + mod * mod) % mod;
}

void solve() {
	cin >> s;
	n = s.length();s = " " + s;
	createhash();
	
	int cnt = 0;
	int l = 1,r = n;
	for (int i = 1;i <= n;i++) {
		if (i - l + 1 > r - i + 1 || l > r) {
			cnt += l <= r;
			break;
		}
		if (l == r) {
			cnt++;
			break;
		}
		
		int len = i - l + 1;
		if (gethash(l,l + len - 1) == gethash(r - len + 1,r)) {
			cnt += 2;
			l += len;
			r -= len;
//			cout << i << "\n";
		}
	}
	
	cout << cnt << '\n';
	
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
	   freopen(thuhien".inp","r",stdin);
	   freopen(thuhien".out","w",stdout);
	}
	
	int test;cin >> test;while (test--) solve();

}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:63:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |            freopen(thuhien".inp","r",stdin);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:64:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |            freopen(thuhien".out","w",stdout);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40