Submission #644370

#	Time	Username	Problem	Language	Result	Execution time	Memory
644370		ymm	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	156 ms	12852 KiB

palindromic

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#define muladd(x, y, z) (((__int128)(x) * (y) + (z)) % mod)

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> s;
		const ll mod = 1'333'333'333'333'333;
		ll pow29 = 1;
		int ans = 0;
		ll h1=0, h2=0;
		Loop (i,0,s.size()) {
			char c1 = s[i]-'a'+1;
			char c2 = s[s.size()-1-i]-'a'+1;
			h1 = muladd(c1, pow29, h1);
			h2 = muladd(h2, 29, c2);
			//cout << h1 << ' ' << h2 << '\n';
			pow29 = muladd(pow29, 29, 0);
			if (h1 == h2) {
				++ans;
				h1 = 0;
				h2 = 0;
				pow29 = 1;
			}
		}
		cout << ans << '\n';
	}

}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
palindromic.cpp:23:3: note: in expansion of macro 'Loop'
   23 |   Loop (i,0,s.size()) {
      |   ^~~~

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