oj.uz

Submission #543249

# Submission time Handle Problem Language Result Execution time Memory
543249 2022-03-30T00:54:30 Z Olympia Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 385 ms 12196 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 272 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 272 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 272 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 3 ms 316 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 272 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 3 ms 316 KB Output is correct
14 Correct 383 ms 12196 KB Output is correct
15 Correct 294 ms 7276 KB Output is correct
16 Correct 385 ms 11488 KB Output is correct
17 Correct 127 ms 6888 KB Output is correct