oj.uz

Submission #146562

# Submission time Handle Problem Language Result Execution time Memory
146562 2019-08-24T12:05:09 Z miguel Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 168 ms 26312 KB 
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
#define L nod<<1
#define R ((nod<<1)|1)
#define mp make_pair
const ll mod = 1000000007;
const ll nmax=1000003;
#define int ll
string s;
int p=27, pw[1000010], n, q, h[1000010];

int g(int l, int r){
    return ((h[r]-h[l-1]*pw[r-l+1])%mod+mod)%mod;
}

int solve(int st, int l, int r, int fin){
    if(l>r) return 0;
    else if(st==l && l==r && r==fin) return 1;
    int s1=g(st, l), s2=g(r, fin);
    if(s1==s2){
        return 2+solve(l+1, l+1, r-1, r-1);
    }
    else{
        if(r-l<=2) return 1;
        return solve(st, l+1, r-1, fin);
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    pw[0]=1;
    for(int i=1; i<=1000001; i++) pw[i]=pw[i-1]*p, pw[i]%=mod;
    cin>>q;
    while(q--){
        cin>>s;
        n=s.size();
        for(int i=1; i<=n; i++) h[i]=(h[i-1]*p+s[i-1])%mod;
        cout<<solve(1, 1, n, n)<<"\n";
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8312 KB Output is correct
2 Correct 15 ms 8188 KB Output is correct
3 Correct 15 ms 8184 KB Output is correct
4 Correct 24 ms 8312 KB Output is correct
5 Correct 14 ms 8184 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8312 KB Output is correct
2 Correct 15 ms 8188 KB Output is correct
3 Correct 15 ms 8184 KB Output is correct
4 Correct 24 ms 8312 KB Output is correct
5 Correct 14 ms 8184 KB Output is correct
6 Correct 14 ms 8184 KB Output is correct
7 Correct 14 ms 8184 KB Output is correct
8 Correct 14 ms 8184 KB Output is correct
9 Correct 14 ms 8184 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8312 KB Output is correct
2 Correct 15 ms 8188 KB Output is correct
3 Correct 15 ms 8184 KB Output is correct
4 Correct 24 ms 8312 KB Output is correct
5 Correct 14 ms 8184 KB Output is correct
6 Correct 14 ms 8184 KB Output is correct
7 Correct 14 ms 8184 KB Output is correct
8 Correct 14 ms 8184 KB Output is correct
9 Correct 14 ms 8184 KB Output is correct
10 Correct 16 ms 8440 KB Output is correct
11 Correct 15 ms 8312 KB Output is correct
12 Correct 16 ms 8440 KB Output is correct
13 Correct 15 ms 8364 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8312 KB Output is correct
2 Correct 15 ms 8188 KB Output is correct
3 Correct 15 ms 8184 KB Output is correct
4 Correct 24 ms 8312 KB Output is correct
5 Correct 14 ms 8184 KB Output is correct
6 Correct 14 ms 8184 KB Output is correct
7 Correct 14 ms 8184 KB Output is correct
8 Correct 14 ms 8184 KB Output is correct
9 Correct 14 ms 8184 KB Output is correct
10 Correct 16 ms 8440 KB Output is correct
11 Correct 15 ms 8312 KB Output is correct
12 Correct 16 ms 8440 KB Output is correct
13 Correct 15 ms 8364 KB Output is correct
14 Correct 168 ms 18812 KB Output is correct
15 Correct 111 ms 22440 KB Output is correct
16 Correct 163 ms 26312 KB Output is correct
17 Correct 100 ms 18076 KB Output is correct