Submission #858626

#	Time	Username	Problem	Language	Result	Execution time	Memory
858626		ngonhatmin	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	137 ms	42268 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;
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;

        //cout << s[1] << ' ' << s[n] << '\n';

        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 bg1 = 1, ed1 = 1, bg2 = n, ed2 = n, result = 0;
        while(ed1 < bg2){
            if (get_hash1(bg1,ed1) == get_hash1(bg2,ed2) &&
                get_hash2(bg1,ed1) == get_hash2(bg2,ed2)){
                result += 2;
                //cout << bg1 << ' ' << ed1 << ' ' << bg2 << ' ' << ed2 << '\n';
                if (ed1 + 1 == bg2) break;
                bg1 = ed1 = ed1 + 1;
                ed2 = bg2 = bg2 - 1;
            }
            else{
                ed1++;
                bg2--;
            }
        }
        if (ed1 + 1 == bg2) cout << result << '\n';
        else cout << result + 1 << '\n';
    }
}

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