oj.uz

Submission #338029

# Submission time Handle Problem Language Result Execution time Memory
338029 2020-12-22T09:35:14 Z rrrr10000 Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 10000 ms 6444 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<PP> vpp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(v) v.begin(),v.end()
#define dupli(v) {sort(all(v));v.erase(unique(all(v)),v.end());}
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define fi first
#define se second
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>void out(T a){cout<<a<<endl;}
template<class T>void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T>void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T>void outvp(T v){for(auto a:v)cout<<'('<<a.fi<<','<<a.se<<')';cout<<endl;}
template<class T>void outvv(T v){for(auto x:v)outv(x);}
template<class T>void outvvp(T v){for(auto x:v)outvp(x);}
const ll inf=1001001001001001001;
vi z_algo(string &s){
    int i=1,j=0;
    vi res(s.size());
    res[0]=s.size();
    while(i<s.size()){
        while(i+j<s.size()&&s[j]==s[i+j])j++;
        res[i]=j;
        if(j==0){
            i++;continue;
        }
        int k=1;
        while(k<j&&k+res[k]<j){
            res[i+k]=res[k];
            k++;
        }
        i+=k;j-=k;
    }
    return res;
}
int main(){
    ll t;cin>>t;
    rep(tt,t){
        ll ans=1;
        string s;cin>>s;
        ll l=0,r=s.size()-1,k=1;
        while(l<r){
            bool same=true;
            rep(i,k)if(s[l-k+1+i]!=s[r+i])same=false;
            if(same){
                ans+=2;k=0;
            }
            l++;r--;k++;
        }
        if(k==1&&s.size()%2==0)ans--;
        out(ans);
    }
}

Compilation message

palindromic.cpp: In function 'vi z_algo(std::string&)':
palindromic.cpp:36:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     while(i<s.size()){
      |           ~^~~~~~~~~
palindromic.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while(i+j<s.size()&&s[j]==s[i+j])j++;
      |               ~~~^~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 35 ms 492 KB Output is correct
11 Correct 32 ms 364 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 3 ms 364 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 35 ms 492 KB Output is correct
11 Correct 32 ms 364 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 3 ms 364 KB Output is correct
14 Execution timed out 10054 ms 6444 KB Time limit exceeded
15 Halted 0 ms 0 KB -