Submission #858438

#	Time	Username	Problem	Language	Result	Execution time	Memory
858438		ngonhatmin	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	8 ms	19036 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for (int i=(a); i>=(b); --i)
#define pb push_back
#define mp make_pair
#define TWO(x) (1<<(x))
#define BIT(s,i) (((s)&TWO(i))>0)
#define ON(s,i) (s |= TWO(i))
#define OFF(s,i) (s &= ~TWO(i))
#define FLIP(s,i) (s ^= TWO(i))
#define vvec vector<vector<int>>

struct ngocon{
    int x,y,z;
};

typedef pair<int,int> pii;
typedef pair<pii,int> piii;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> pipi;

const int h4[4] = {1,0,-1,0}; /// 4 huong
const int c4[4] = {0,1,0,-1}; /// 4 huong
const int h8[8] = {-1,-1,-1,0,1,1,1,0}; /// 8 huong
const int c8[8] = {-1,0,1,1,1,0,-1,-1}; /// 8 huong
const int cv1[8] = {1,2,2,1,-1,-2,-2,-1}; /// 8 huong quan ma
const int cv2[8] = {-2,-1,1,2,2,1,-1,-2}; /// 8 huong quan ma
const int mod1 = 1e9 + 7; /// chia du
const int mod2 = 1e6 + 3;
const int base = 26; /// ma hoa
const int oo = 1e16;
const int N = 1e6 + 2;

int n,result;
int Pow1[N],Pow2[N],Hash1[N],Hash2[N];
string s;

int get_hash1(int i, int j){
    return (Hash1[j] - (Hash1[i-1]*Pow1[j-i+1]) % mod1 + mod1) % mod1;
}

int get_hash2(int i, int j){
    return (Hash2[j] - (Hash2[i-1]*Pow2[j-i+1]) % mod2 + mod2) % mod2;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);

    Pow1[0] = Pow2[0] = 1;
    FOR(i,1,1000000){
        Pow1[i] = (Pow1[i-1] * base) % mod1;
        Pow2[i] = (Pow2[i-1] * base) % mod2;
    }

    int t; cin >> t;
    while(t--){
        cin >> s;
        n = s.size(); s = ' ' + s;

        Hash1[0] = Hash2[0] = 0;
        FOR(i,1,n){
            Hash1[i] = (Hash1[i-1] * base + s[i] - 'a') % mod1;
            Hash2[i] = (Hash2[i-1] * base + s[i] - 'a') % mod2;
        }

        int pos1 = 1, pos2 = n; result = 0;
        FOR(i,1,n/2){
            int tmp = pos2 - (i - pos1 + 1) + 1;
            if (get_hash1(pos1,i) == get_hash1(tmp,pos2) && get_hash2(pos1,i) == get_hash2(tmp,pos2)){
                result += 2;
                pos1 = i + 1;
                pos2 = tmp - 1;
            }
        }
        cout << result + 1 << '\n';
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40