Submission #1095052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095052		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	11 ms	8284 KiB

palindromic

//------------------------------------\
//   ------------------------------   \
//  |    created by Pham Phuongg   |  \
//  |       phamvuphuong2008       |  \
//  |     THPT CHUYEN HA TINH      |  \
//  |      HA TINH, VIET NAM       |  \
//  |    Bé Phương from TK4-CHT    |  \
//   ------------------------------   \
//------------------------------------\


#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define ii pair<int ,int >
#define endl '\n'
#define iii pair<int,ii>
#define pb push_back
#define task "main"
#define base 341
using namespace std;
const int maxn = 1e6+5;
const int lim = 1e6;
int mod = 1e9+7;
int p[maxn], f[maxn];
string s;
int add(int a, int b) {
	return (a + b)%mod;
}
int mul(int a, int b) {
	return ((a%mod)*(b%mod))%mod;
}
int sub(int a, int b) {
	return ((a-b)%mod+mod)%mod;
}
int get(int l, int r) {
	return sub(f[r], mul(f[l-1], p[r-l+1]));
}
void solve(){
	cin >> s;
	int n = s.length();  
	s = " " + s;
	for (int i = 1; i <= n; i++) f[i] = add(mul(f[i-1], base), s[i] - 'a' + 1);
	int l = 1, r = n, cnt = 0;
	if (get(3,4) == get(r,r)) cout << "YES" << endl;
	while(l <= r) {
		int res = -1;
		for (int i = 0; i <= n; i++) {
			if (get(l,l+i) == get(r-i,r)) {
				res = i;
				break;
			}
		}
//		cout << res << " " << l << " " << r << endl;
		if (l == r-res && l + res == r) break;
		l += res + 1;
		r -= (res + 1);
		cnt += 2;
	}
	cout << cnt + 1;
}
main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    p[0] = 1;
    for (int i = 1; i <= lim; i++) p[i] = mul(p[i-1], base);
    int t=1;
    cin>>t;
    while(t--){
        solve();
        cout << endl;
    }
}

Compilation message (stderr)

palindromic.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //------------------------------------\
      | ^
palindromic.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main() {
      | ^~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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