oj.uz

Submission #1034912

# Submission time Handle Problem Language Result Execution time Memory
1034912 2024-07-25T21:24:39 Z MarwenElarbi Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 159 ms 28648 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e6+5;
const int MOD=1e9+9;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
vector<ll> pw={1};
vector<ll> p_hash(nax);
long long B=9973;
void compute_hash(string s){
    while(pw.size()<s.size()){
        pw.pb((pw.back()*B)%MOD);
    }
    p_hash[0]=0;
    for (int i = 0; i < s.size(); ++i)
    {
        p_hash[i+1]=((p_hash[i]*B)%MOD+s[i])%MOD;
    }   
    return;
}
int get_hash(int l,int r){
    long long ans=(p_hash[r+1]-(p_hash[l]*pw[r-l+1]));
    return (ans%MOD + MOD)%MOD;
}
int main()
{
    optimise;
    int test_cases;
    cin>>test_cases;
    while(test_cases--){
        string t;
        cin>>t;
        int n=t.size()+1;
        reverse(t.begin(),t.end());
        t.pb(' ');
        reverse(t.begin(),t.end());
        compute_hash(t);
        int ans=0;
        int lst=1;
        bool test=false;
        for (int i = 1; i <= n/2; ++i)
        {
            if(get_hash(lst,i)==get_hash(n-i,n-lst)){
                ans+=2;
                if(i==n/2&&n%2==0&&i==lst) ans--;
                lst=i+1;
            }else if(i==n/2) ans++;
        }
        cout <<ans<<endl;
    }
}

Compilation message

palindromic.cpp: In function 'void compute_hash(std::string)':
palindromic.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0; i < s.size(); ++i)
      |                     ~~^~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:50:14: warning: unused variable 'test' [-Wunused-variable]
   50 |         bool test=false;
      |              ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8264 KB Output is correct
7 Correct 3 ms 8292 KB Output is correct
8 Correct 3 ms 8284 KB Output is correct
9 Correct 3 ms 8284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8264 KB Output is correct
7 Correct 3 ms 8292 KB Output is correct
8 Correct 3 ms 8284 KB Output is correct
9 Correct 3 ms 8284 KB Output is correct
10 Correct 5 ms 8536 KB Output is correct
11 Correct 5 ms 8540 KB Output is correct
12 Correct 4 ms 8632 KB Output is correct
13 Correct 5 ms 8564 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8264 KB Output is correct
7 Correct 3 ms 8292 KB Output is correct
8 Correct 3 ms 8284 KB Output is correct
9 Correct 3 ms 8284 KB Output is correct
10 Correct 5 ms 8536 KB Output is correct
11 Correct 5 ms 8540 KB Output is correct
12 Correct 4 ms 8632 KB Output is correct
13 Correct 5 ms 8564 KB Output is correct
14 Correct 159 ms 28648 KB Output is correct
15 Correct 92 ms 23808 KB Output is correct
16 Correct 152 ms 28088 KB Output is correct
17 Correct 84 ms 18892 KB Output is correct