Submission #536471

#	Time	Username	Problem	Language	Result	Execution time	Memory
536471		Asymmetry	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	174 ms	18804 KiB

palindromic

//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

const int N = 1'000'100;
const int MOD = 1e9 + 7;
const int P = 29;
int n;
int hs[N];
int pot[N];
char s[N];

long long has(int a, int b) {
	return (hs[b] - (long long)hs[a - 1] * pot[b - a + 1] % MOD + MOD) % MOD;
}

void solve() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	pot[0] = 1;
	for (int i = 1; i <= n; ++i) {
		hs[i] = ((long long)hs[i - 1] * P + s[i] - 'a' + 1) % MOD;
		pot[i] = (long long)pot[i - 1] * P % MOD;
	}
	int odp = 0;
	int ost = 1;
	for (int i = 1; i <= n / 2; ++i) {
		if (has(ost, i) == has(n - i + 1, n - ost + 1)) {
			odp += 2;
			ost = i + 1;
		}
	}
	if (n & 1 || (!(n & 1) && ost <= n / 2)) {
		++odp;
	}
	printf("%d\n", odp);
}

int main() {
	int q=1;
	scanf("%d", &q);
	while(q--) {
		solve();
	}
	return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%s", s + 1);
      |  ~~~~~^~~~~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~

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