oj.uz

Submission #393316

# Submission time Handle Problem Language Result Execution time Memory
393316 2021-04-23T07:42:11 Z rumen_m Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 1 ms 332 KB 
# include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int base = 27;
const int maxn = 1e6+5;
int hashes[maxn];
int poww[maxn];
int find_hash(int from, int to)
{
    int pref = (hashes[from-1]*poww[to-from+1])%MOD;
    int ans = (hashes[to]+MOD-pref)%MOD;
    return ans;
}
void solve()
{
    string s;
    cin>>s;
    int ans = 0;
    poww[0] = 1;
    hashes[0] = 0;
    int i;
    for(i = 1; i<=s.size();i++)
    {
        int ch = s[i-1]-'a'+1;
        poww[i] = (poww[i-1]*base)%MOD;
        hashes[i] = (hashes[i-1]*base + ch)%MOD;
    }
    int prev = 1;
    int from = 1;
    int last = s.size();
    int endd = s.size();
    bool fl = false;
    while(from<last)
    {
        if(find_hash(prev,from)==find_hash(last,endd))
        {
            fl = false;
            ans+=2;
           // cout<<"  "<<from<<endl;
            prev = from+1;
            endd = last-1;
            from++;
            last--;
            continue;
        }
        fl = true;
        from++;
        last--;
    }
    if(fl||from==last)ans++;
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
        solve();
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -