Submission #1310928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310928		mpdoge	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	86 ms	17184 KiB

palindromic

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <cmath>
// Dla macOs zachowaj includy w przeciwnym wypadku zastąp "#include <bits/stdc++.h> "

// szybki kod 

#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for(int i = a;i <= b; i++)
#define per(i, a, b) for(int i = a;i >= b; i--)
#define pb push_back
#define ins insert
#define st first
#define nd second;
#define test  int tc; cin>>tc; while(tc--)


// struktury danych 

#define smldi set<map<long double, int > >
#define spumldidsi set<pair<unordered_map<long double, int>, deque<set<long long> > > > 

// funkcje wspomagajace debugowanie programu

#define printv(a) { for(auto u : a) cout<<u<<" "; cout<<"/n"; }
#define debug(x) cerr << #x << " = " << x << endl;

// usingi 

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using si = set<int>;
using mii = map<int,int>;
using bigi = __int128;

const ll p = 29, MOD = 1000000007;

ll hashe[1000005];
ll pot[1000005];

string s;
int n;

ll hash_(int a,int b){
    if(a == 0) return hashe[b];
    ll h1 = hashe[b], h2 = hashe[a-1];
    //cout<<" mamy 2 hashe "<<h1<<" "<<h2<<" i 2 mnozemy razy "<<p<<" do "<<b-a + 1<<endl;
    return (h1 - (h2 * pot[b - a + 1]) + (MOD * MOD)) % MOD;
}

void hashuj(){
    hashe[0] = s[0];
    //cout<<" pierwszy to "<<hashe[0]<<endl;
    for(int i = 1;i < n;i++){
        hashe[i] = (hashe[i - 1] * p + s[i]) % MOD;
        //cout<<" ustawiamy nowy hash na poprzedni razy "<<p<<" "<<hashe[i]<<endl;
    }
}

bool czy_te_same(int a,int b,int c,int d){
    return hash_(a,b) == hash_(c,d);
}

void solve(){
    cin>>s;
    int akt = 0, wyn = 0;
    n = s.size();
    hashuj();
    //cout<<hash_(0,1)<<endl<<hash_(2,3)<<endl;
    for(int i=0;i < n/2;i++){
        if(czy_te_same(akt, i, n - i - 1, n - akt - 1)){
            //cout<<" znalezlismy te same na "<<akt<<" "<<i<<endl;
            akt = i+1;
            wyn+= 2;
        }
    }
    if(akt != n/2 + n%2){
        wyn++;
    }
    cout<<wyn<<endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    pot[0] = 1;
    for(int i=1;i<1000000;i++){
        pot[i] = (pot[i-1] * p) % MOD;
    }
    test{
        solve();
    }
    return 0;
}

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