oj.uz

Submission #116254

# Submission time Handle Problem Language Result Execution time Memory
116254 2019-06-11T15:28:39 Z Meloric Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 577 ms 42868 KB 
#include <bits/stdc++.h>
#define pb push_back
#define X first
#define Y second
#define pii pair<int, int>
#define int int64_t
#define pow pww
using namespace std;
int mod = 1e9+7;
vector<int>hsh, pow;

bool same(int l, int r, int len, vector<int>&wrd){
    for(int i = 0; i<=len; i++){
        if(wrd[l+i] != wrd[r+i-len])return false;
    }
    return true;
}
int hval(int l, int r){
    int ans;
    r++;
    ans = hsh[r] - hsh[l]*pow[r-l+1];
    ans %= mod;
    if(ans<0)ans+=mod;
    return ans;
}
int dp(int l, int r, vector<int>&wrd){
    if(r<l)return 0;
    for(int i = 0; i+l < r-i ;i++){
        if(hval(l, l+i) == hval(r-i, r) && same(l, r, i, wrd))return dp(l+i+1, r-i-1, wrd)+2;
    }
    return 1;
}
void solve(){
    hsh.clear(); pow.clear();
    string in; vector<int> wrd;
    cin >> in;
    for(auto i : in)wrd.pb(i-'a');
    pow.pb(0); hsh.pb(0); pow.pb(1);
    for(int i = 0; i < wrd.size(); i++){
        hsh.pb(hsh.back()*131+wrd[i]);
        hsh.back()%=mod;
        pow.pb(pow.back()*131);
        pow.back() %=mod;
    }
    //for(int i : wrd)cout << i <<' ';
    cout << dp(0, wrd.size()-1, wrd)<< '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

palindromic.cpp: In function 'void solve()':
palindromic.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < wrd.size(); i++){
                    ~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 2 ms 428 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 2 ms 428 KB Output is correct
10 Correct 7 ms 896 KB Output is correct
11 Correct 5 ms 892 KB Output is correct
12 Correct 7 ms 896 KB Output is correct
13 Correct 7 ms 896 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 2 ms 428 KB Output is correct
10 Correct 7 ms 896 KB Output is correct
11 Correct 5 ms 892 KB Output is correct
12 Correct 7 ms 896 KB Output is correct
13 Correct 7 ms 896 KB Output is correct
14 Correct 577 ms 41900 KB Output is correct
15 Correct 319 ms 37828 KB Output is correct
16 Correct 572 ms 42868 KB Output is correct
17 Correct 349 ms 22924 KB Output is correct