Submission #858422

#	Time	Username	Problem	Language	Result	Execution time	Memory
858422		ngonhatmin	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	6 ms	9564 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 mod = 1e9 + 7; /// chia du
const int base = 26; /// ma hoa
const int oo = 1e16;
const int N = 1e6 + 2;

int n,result;
int Pow[N],Hash[N];
string s;

int get_hash(int i, int j){
    return (Hash[j] - Hash[i-1]*Pow[j-i+1] % mod + mod) % mod;
}

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

    Pow[0] = 1;
    FOR(i,1,1000000) Pow[i] = (Pow[i-1] * base) % mod;

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

        FOR(i,1,n) Hash[i] = (Hash[i-1] * base + s[i] - 'a') % mod;
        int pos1 = 1, pos2 = n; result = 0;
        FOR(i,1,n/2){
            int tmp = pos2 - (i - pos1 + 1) + 1;
            //cout << pos1 << ' ' << i << ' ' << tmp << ' ' << pos2 << "  " << get_hash(pos1,i) << ' ' << get_hash(tmp,pos2) << '\n';
            if (get_hash(pos1,i) == get_hash(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