oj.uz

Submission #545826

# Submission time Handle Problem Language Result Execution time Memory
545826 2022-04-05T14:08:35 Z Ai7081 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 53 ms 15056 KB 
#include <bits/stdc++.h>
using namespace std;
#define long long long

const long mod = 1e9+7;
const long key = 31;

long t, out, l, r, now, po[500005];
string s;
stack<char> st;
bool ok;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    po[0] = 1;
    for (long i=1; i<=500000; i++) po[i] = (po[i-1] * key) % mod;
    cin >> t;
    while (t--) {
        cin >> s;
        ok = false;
        out = l = r = now = 0;
        for (long i=0; i<s.size()/2; i++) {
            l *= key, l += (s[i]-'a'), l %= mod;
            r += (s[s.size()-1-i]-'a')*po[now], r %= mod;
            if (l == r) now = l = r = 0, out += 2;
            else now++;
        }
        (s.size()%2 || now) ? cout << out+1 << endl : cout << out << endl;
    }
    return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:22:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (long i=0; i<s.size()/2; i++) {
      |                        ~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 4 ms 4180 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 4 ms 4180 KB Output is correct
5 Correct 5 ms 4180 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 4 ms 4180 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 4 ms 4180 KB Output is correct
5 Correct 5 ms 4180 KB Output is correct
6 Correct 5 ms 4180 KB Output is correct
7 Correct 5 ms 4180 KB Output is correct
8 Correct 4 ms 4244 KB Output is correct
9 Correct 5 ms 4180 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 4 ms 4180 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 4 ms 4180 KB Output is correct
5 Correct 5 ms 4180 KB Output is correct
6 Correct 5 ms 4180 KB Output is correct
7 Correct 5 ms 4180 KB Output is correct
8 Correct 4 ms 4244 KB Output is correct
9 Correct 5 ms 4180 KB Output is correct
10 Correct 5 ms 4308 KB Output is correct
11 Correct 5 ms 4244 KB Output is correct
12 Correct 4 ms 4308 KB Output is correct
13 Correct 5 ms 4308 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 4 ms 4180 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 4 ms 4180 KB Output is correct
5 Correct 5 ms 4180 KB Output is correct
6 Correct 5 ms 4180 KB Output is correct
7 Correct 5 ms 4180 KB Output is correct
8 Correct 4 ms 4244 KB Output is correct
9 Correct 5 ms 4180 KB Output is correct
10 Correct 5 ms 4308 KB Output is correct
11 Correct 5 ms 4244 KB Output is correct
12 Correct 4 ms 4308 KB Output is correct
13 Correct 5 ms 4308 KB Output is correct
14 Correct 50 ms 15056 KB Output is correct
15 Correct 32 ms 10444 KB Output is correct
16 Correct 53 ms 14528 KB Output is correct
17 Correct 27 ms 9972 KB Output is correct