oj.uz

Submission #540424

# Submission time Handle Problem Language Result Execution time Memory
540424 2022-03-20T10:30:10 Z Vladth11 Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 147 ms 16816 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 1000001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll nr_of_bits = 16;

class Hash{
    public:
    ll val, p;
    ll base, mod;
    Hash(ll _base, ll _mod){
        base = _base;
        mod = _mod;
    }
    void clear(){
        val = 0;
        p = 1;
    }
    void push_back(ll x){
        val = val * base + x;
        val %= mod;
        p *= base;
        p %= mod;
    }
    void push_front(ll x){
        val = (p * x) % mod + val;
        val %= mod;
        p *= base;
        p %= mod;
    }
};

Hash x(31, 1000000009), y(31, 1000000009);
int v[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        for(int i = 0; i < s.size(); i++){
            v[i + 1] = s[i] - 'a' + 1;
        }
        x.clear();
        y.clear();
        int cnt = 0, lasti = 0, lastj = 2e9;
        int i = 1, j = s.size();
        while(i < j){
            x.push_back(v[i]);
            y.push_front(v[j]);
            if(x.val == y.val){
                cnt += 2;
                lasti = i;
                lastj = j;
                x.clear();
                y.clear();
            }
            i++;
            j--;
        }
        if(lasti != lastj - 1){
            cnt++;
        }
        cout << cnt << "\n";
    }
    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 336 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 596 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 126 ms 16816 KB Output is correct
15 Correct 75 ms 11644 KB Output is correct
16 Correct 147 ms 15736 KB Output is correct
17 Correct 64 ms 8920 KB Output is correct