Submission #279710

#	Time	Username	Problem	Language	Result	Execution time	Memory
279710		BeanZ	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	195 ms	28552 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 15;
const int base = 311;
const int mod = 1e9 + 7;
ll h[1000006], p[1000006];
ll get(ll i, ll j){
        return (h[j] - p[j - i + 1] * h[i - 1] + (ll)mod * mod) % mod;
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("VietCT.INP", "r")){
                freopen("VietCT.INP", "r", stdin);
                freopen("VietCT.OUT", "w", stdout);
        }
        ll t;
        cin >> t;
        while (t--){
                string s;
                cin >> s;
                ll n = s.length();
                if (n == 1){
                        cout << 1 << endl;
                        continue;
                }
                s = " " + s;
                p[0] = 1;
                for (int i = 1; i <= n; i++){
                        p[i] = p[i - 1] * base % mod;
                }
                for (int i = 1; i <= n; i++){
                        h[i] = (h[i - 1] * base + (s[i] - 'a') + 1) % mod;
                }
                ll lb = 1, rb = 1, le = n, re = n;
                ll ans = 0;
                while (true){
                        if (get(lb, rb) == get(le, re)){
                                lb = rb + 1;
                                re = le - 1;
                                ans += 2;
                                rb++;
                                le--;
                                if (rb > le){
                                        cout << ans << endl;
                                        break;
                                }
                                if (rb == le){
                                        cout << ans + 1 << endl;
                                        break;
                                }
                        } else {
                                rb++;
                                le--;
                                if (rb >= le){
                                        cout << ans + 1 << endl;
                                        break;
                                }
                        }
                }
        }
}
/*
*/

Compilation message (stderr)

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

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