oj.uz

답안 #1116574

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1116574 2024-11-21T20:23:36 Z PagodePaiva Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 49380 KB 
#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second

using namespace std;

const int N = 1000010;
const int p = 1e9+7;
const int q = 1e9+9;
const int b = 127;
int pot[N][2];
int potinv[N][2];

int binpow(int a, int b, int mod){
    if(b == 0) return 1;
    int t = binpow(a, b/2, mod);
    t *= t;
    t %= mod;
    if(b%2 == 0) return t;
    else return (a*t)%mod;
}

struct hs{
    pair <int, int> pref[N];
    void build(string s){
        pref[0] = {0, 0};
        for(int i = 0;i < s.size();i++){
            pref[i+1].fr = (pref[i].fr + ((s[i]-'a'+1)*pot[i][0])%p)%p;
            pref[i+1].sc = (pref[i].sc+((s[i]-'a'+1)*pot[i][1])%q)%q;
        }
    }
    pair <int, int> query(int l, int r){
        l++;
        r++;
        return {(((pref[r].first+p-pref[l-1].first)%p)*potinv[l-1][0])%p, (((pref[r].second+q-pref[l-1].second)%q)*potinv[l-1][1])%q};
    }
    bool get(int l1, int r1, int l2, int r2){
        if(query(l1, r1) == query(l2, r2)) return true;
        return false;
    }
} h;
int res[N];

void solve(){
    string s;
    cin >> s;
    h.build(s);
    int n = s.size();
    if(n == 1){
        cout << 1 << '\n';
        return;
    }
    int st = (n%2 == 0 ? (n-1)/2 : n/2);
    res[st+1] = 0;
    res[st] = (n%2 == 1 ? 1 : (s[st] == s[st+1] ? 2 : 1));
    for(int i = st-1;i >= 0;i--){
        int r = (n%2 == 1 ? st+st-i : st+st-i+1);
        //cout << i << ' ' << r << '\n';
        res[i] = 1;
        for(int j = i;j <= st;j++){
          //  cout << i << ' ' << j << ' ' << r-(j-i) << ' ' << r << ' ' << h.get(i, j, r-(j-i), r) << '\n';
            if(h.get(i, j, r-(j-i), r)){
                res[i] = max(res[i], res[j+1]+2);
            }
        }
    }
    cout << res[0] << '\n';
}

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int t;
    cin >> t;
    pot[0][0] = pot[0][1] = 1;
    potinv[0][0] = potinv[0][1] = 1;
    for(int i = 1;i < N;i++){
        pot[i][0] = (pot[i-1][0]*b)%p;
        pot[i][1] = (pot[i-1][1]*b)%q;
        potinv[i][0] = binpow(pot[i][0], p-2, p);
        potinv[i][1] = binpow(pot[i][1], q-2, q);
    }
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

palindromic.cpp: In member function 'void hs::build(std::string)':
palindromic.cpp:28:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i = 0;i < s.size();i++){
      |                       ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 443 ms 34376 KB Output is correct
2 Correct 440 ms 34544 KB Output is correct
3 Correct 438 ms 34512 KB Output is correct
4 Correct 443 ms 32328 KB Output is correct
5 Correct 456 ms 32468 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 443 ms 34376 KB Output is correct
2 Correct 440 ms 34544 KB Output is correct
3 Correct 438 ms 34512 KB Output is correct
4 Correct 443 ms 32328 KB Output is correct
5 Correct 456 ms 32468 KB Output is correct
6 Correct 454 ms 32328 KB Output is correct
7 Correct 452 ms 32328 KB Output is correct
8 Correct 462 ms 32292 KB Output is correct
9 Correct 474 ms 32328 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 443 ms 34376 KB Output is correct
2 Correct 440 ms 34544 KB Output is correct
3 Correct 438 ms 34512 KB Output is correct
4 Correct 443 ms 32328 KB Output is correct
5 Correct 456 ms 32468 KB Output is correct
6 Correct 454 ms 32328 KB Output is correct
7 Correct 452 ms 32328 KB Output is correct
8 Correct 462 ms 32292 KB Output is correct
9 Correct 474 ms 32328 KB Output is correct
10 Correct 1524 ms 32740 KB Output is correct
11 Correct 779 ms 32584 KB Output is correct
12 Correct 1100 ms 32740 KB Output is correct
13 Correct 927 ms 32692 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 443 ms 34376 KB Output is correct
2 Correct 440 ms 34544 KB Output is correct
3 Correct 438 ms 34512 KB Output is correct
4 Correct 443 ms 32328 KB Output is correct
5 Correct 456 ms 32468 KB Output is correct
6 Correct 454 ms 32328 KB Output is correct
7 Correct 452 ms 32328 KB Output is correct
8 Correct 462 ms 32292 KB Output is correct
9 Correct 474 ms 32328 KB Output is correct
10 Correct 1524 ms 32740 KB Output is correct
11 Correct 779 ms 32584 KB Output is correct
12 Correct 1100 ms 32740 KB Output is correct
13 Correct 927 ms 32692 KB Output is correct
14 Execution timed out 10052 ms 49380 KB Time limit exceeded
15 Halted 0 ms 0 KB -