oj.uz

Submission #146561

# Submission time Handle Problem Language Result Execution time Memory
146561 2019-08-24T12:04:46 Z miguel Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 161 ms 18704 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<=100001; 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 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1148 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1148 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 5 ms 1272 KB Output is correct
11 Correct 4 ms 1272 KB Output is correct
12 Correct 5 ms 1272 KB Output is correct
13 Correct 4 ms 1144 KB Output is correct
14 Incorrect 161 ms 18704 KB Output isn't correct
15 Halted 0 ms 0 KB -