oj.uz

Submission #250637

# Submission time Handle Problem Language Result Execution time Memory
250637 2020-07-18T14:49:27 Z Sorting Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 10000 ms 21916 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int k_N = 1e6 + 3;
const int cnt_Mod = 1;
const array<ll, cnt_Mod> k_Mod{(int)1e9 + 7}, k_Base{293};

int dp[k_N];
string s;
int n;

array<ll, cnt_Mod> h[k_N], b_pow[k_N];
vector<int> pos[256];
int idx[256];

ll get_hash(int l, int r, int idx){
    if(l == 0) return h[r][idx];
    ll ans = (h[r][idx] - h[l - 1][idx] * b_pow[r - l + 1][idx]) % k_Mod[idx];
    return (ans < 0) ? (ans + k_Mod[idx]) : ans;
}

bool equal(int l1, int r1, int l2, int r2){
    for(int i = 0; i < cnt_Mod; ++i)
        if(get_hash(l1, r1, i) != get_hash(l2, r2, i))
            return false;
    return true;
}

void init_hashing(){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < cnt_Mod; ++j){
            if(i == 0)
                h[i][j] = s[i];
            else
                h[i][j] = (h[i - 1][j] * k_Base[j] + s[i]) % k_Mod[j];
        }
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < cnt_Mod; ++j){
            if(i == 0)
                b_pow[i][j] = 1;
            else
                b_pow[i][j] = b_pow[i - 1][j] * k_Base[j] % k_Mod[j];
        }
    }
}

void solve(){
    cin >> s;
    n = (int)s.size();

    if(n == 1){
        cout << "1\n";
        return;
    }


    init_hashing();
    for(int i = 0; i < n; ++i)
        pos[s[i]].push_back(i);

    int mid = (n - 1) / 2, mid2 = (n - 2) / 2;
    dp[mid + 1] = 0;
    for(int i = mid; i >= 0; --i){
        dp[i] = 1;
        for(int k = (int)pos[s[i]].size() - 1; k >= 0; --k){
            int j = pos[s[i]][k];
            //cout << i << " " << j << " before\n";
            if(j > n - i - 1) continue;
            if(n - j - 1 >= j) break;
            //cout << i << " " << j << "\n";
            if(equal(i, n - j - 1, j, n - i - 1))
                dp[i] = max(dp[n - j] + 2, dp[i]);
        }
    }

    cout << dp[0] << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--)
        solve();
}

Compilation message

palindromic.cpp: In function 'void solve()':
palindromic.cpp:64:17: warning: array subscript has type 'char' [-Wchar-subscripts]
         pos[s[i]].push_back(i);
                 ^
palindromic.cpp:70:34: warning: array subscript has type 'char' [-Wchar-subscripts]
         for(int k = (int)pos[s[i]].size() - 1; k >= 0; --k){
                                  ^
palindromic.cpp:71:29: warning: array subscript has type 'char' [-Wchar-subscripts]
             int j = pos[s[i]][k];
                             ^
palindromic.cpp:66:28: warning: unused variable 'mid2' [-Wunused-variable]
     int mid = (n - 1) / 2, mid2 = (n - 2) / 2;
                            ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1161 ms 1284 KB Output is correct
11 Correct 388 ms 940 KB Output is correct
12 Correct 756 ms 1348 KB Output is correct
13 Correct 541 ms 1064 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1161 ms 1284 KB Output is correct
11 Correct 388 ms 940 KB Output is correct
12 Correct 756 ms 1348 KB Output is correct
13 Correct 541 ms 1064 KB Output is correct
14 Execution timed out 10023 ms 21916 KB Time limit exceeded
15 Halted 0 ms 0 KB -