oj.uz

Submission #320394

# Submission time Handle Problem Language Result Execution time Memory
320394 2020-11-08T15:10:14 Z suto Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 214 ms 28584 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef string str;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define Mp                          make_pair
#define pb(x)                       push_back(x)
#define pf(x)                       push_front(x)
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << " = " << x << endl
#define SZ(x)                       ll(x.size())
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const ll MAXN = 1e6 + 10;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

ll po[MAXN] , hsh[MAXN];

int main(){

    fast_io;
    po[0] = 1;
    for(int i = 1; i < MAXN; i++){
        po[i] = po[i - 1] * 737 % MOD;
    }
    ll t;
    cin >> t;
    while (t --){
        str s;
        cin >> s;
        ll n = s.size();
        for(int i = 1; i <= n; i++){
            hsh[i] = (hsh[i - 1] * 737 % MOD + (s[i - 1] - 'a' + 1))% MOD;
        }
        ll l = 1 , r = n , ans = 0;
        while(r >= l){
            ll v = l , u = r;
            bool d = false;
            while(u > v){
                if((hsh[v] - hsh[l - 1] * po[v - l + 1] % MOD + MOD) % MOD == (hsh[r] - hsh[u - 1] * po[r - u + 1] % MOD + MOD) % MOD){
                    v ++;
                    u --;
                    ans += 2;
                    d = true;
                    break;
                }
                v ++;
                u --;
            }
            if(!d){
                ans ++;
                break;
            }
            l = v;
            r = u;
        }
        cout << ans << endl;
    }

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8332 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 9 ms 8172 KB Output is correct
4 Correct 9 ms 8172 KB Output is correct
5 Correct 9 ms 8172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8332 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 9 ms 8172 KB Output is correct
4 Correct 9 ms 8172 KB Output is correct
5 Correct 9 ms 8172 KB Output is correct
6 Correct 9 ms 8172 KB Output is correct
7 Correct 9 ms 8172 KB Output is correct
8 Correct 10 ms 8172 KB Output is correct
9 Correct 10 ms 8172 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8332 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 9 ms 8172 KB Output is correct
4 Correct 9 ms 8172 KB Output is correct
5 Correct 9 ms 8172 KB Output is correct
6 Correct 9 ms 8172 KB Output is correct
7 Correct 9 ms 8172 KB Output is correct
8 Correct 10 ms 8172 KB Output is correct
9 Correct 10 ms 8172 KB Output is correct
10 Correct 13 ms 8428 KB Output is correct
11 Correct 11 ms 8300 KB Output is correct
12 Correct 11 ms 8428 KB Output is correct
13 Correct 11 ms 8428 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8332 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 9 ms 8172 KB Output is correct
4 Correct 9 ms 8172 KB Output is correct
5 Correct 9 ms 8172 KB Output is correct
6 Correct 9 ms 8172 KB Output is correct
7 Correct 9 ms 8172 KB Output is correct
8 Correct 10 ms 8172 KB Output is correct
9 Correct 10 ms 8172 KB Output is correct
10 Correct 13 ms 8428 KB Output is correct
11 Correct 11 ms 8300 KB Output is correct
12 Correct 11 ms 8428 KB Output is correct
13 Correct 11 ms 8428 KB Output is correct
14 Correct 214 ms 28584 KB Output is correct
15 Correct 108 ms 23432 KB Output is correct
16 Correct 179 ms 27612 KB Output is correct
17 Correct 124 ms 19004 KB Output is correct