Submission #543249

#	Time	Username	Problem	Language	Result	Execution time	Memory
543249		Olympia	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	385 ms	12196 KiB

palindromic

#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#define ll long long
using namespace std;
const int MOD = 1e9 + 7;
ll binPow (ll x, ll y) {
    ll ans = 1;
    ll res = x;
    while (y > 0) {
        if (y & 1) {
            ans *= res;
            ans %= MOD;
        }
        res *= res;
        res %= MOD;
        y >>= 1;
    }
    return ans;
}
void solve() {
    string s;
    cin >> s;
    ll l = 0;
    ll r = 0;
    ll len = 0;
    int cnt = 0;
    for (int i = 0; i < s.length()/2; i++) {
        l += (binPow(10, len) * (s[i] - 'a')) % MOD;
        r = ((10 * r) % MOD + (s[s.length() - i -1 ] - 'a')) % MOD;
        l %= MOD, r %= MOD;
        len++;
        if (l == r) {
            cnt += 2;
            l = r = len = 0;
        } else if (s.length() % 2 == 0 && i == s.length()/2 - 1) {
            cnt++;
        }
    }
    if (s.length() % 2 == 1) {
        cnt++;
    }
    cout << cnt << endl;
}
int main() {
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < s.length()/2; i++) {
      |                     ~~^~~~~~~~~~~~~~
palindromic.cpp:44:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         } else if (s.length() % 2 == 0 && i == s.length()/2 - 1) {
      |                                           ~~^~~~~~~~~~~~~~~~~~~

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