oj.uz

Submission #240196

# Submission time Handle Problem Language Result Execution time Memory
240196 2020-06-18T13:56:08 Z Nucleist Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 385 ms 40360 KB 
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<int>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define EPS 0.000001
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}
vector<ll> pi;
ll mi=MOD;
ve compute_hash(string const& s) {
    const ll p = 31;
    const ll m = MOD;
    long long hash_value = 0;
    long long p_pow = 1;
    ve cur;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        pi.pb(p_pow);
        p_pow = (p_pow * p) % m;
        cur.pb(hash_value);
    }
    return cur;
}
ve compute_hash1(string const& s) {
    const ll p = 31;
    const ll m = MOD;
    long long hash_value = 0;
    long long p_pow = 1;
    ve cur;
    for (ll i = s.size()-1; i >= 0; --i)
    {
      char c=s[i];
      hash_value = (hash_value*31)%m; 
      hash_value = (hash_value + (c - 'a' + 1)) % m;
      p_pow = (p_pow * p) % m;
      cur.pb(hash_value);
    }
    return cur;
}
int main()
{
  //freopen("tit.txt","r",stdin);
  //freopen("out","w",stdout);
  flash;
  ll nb;
  cin>>nb;
  ve now,now1;
  while(nb--){
    pi.clear();
    string ka;
    cin>>ka;
    now=compute_hash(ka);
    now1=compute_hash1(ka);
    reverse(all(now1));
    ll n=sz(ka);
    ll last=INF;
    ll last1=INF;
    ll ans=0;
    ll kobr=n;
    for (int i = 0; i < ka.size()/2; ++i)
    {
      ll cur=0,cur1=0;
      if(last!=INF){
        cur=((ll)(now1[n-i-1]-((ll)((now1[n-last1-1]*pi[i-last1]))%mi)+mi))%mi;
        cur=(ll)((cur*pi[last1+1]))%mi;
        cur1=((ll)(now[i]-now[last]+mi))%mi;
      }
      else{
        cur=(now1[n-i-1]);
        cur1=(now[i]);
      }
      if(cur==cur1){
        if(last!=INF)kobr-=(i-last)*2;
        else kobr-=(i+1)*2;
        last=i;
        last1=i;
        ans+=2;
      }
    }
    if(kobr)ans++;
    cout<<ans<<'\n';
  }
  return 0;
}
//code the AC sol !
// BS/queue/map

Compilation message

palindromic.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
palindromic.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
palindromic.cpp: In function 'int main()':
palindromic.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ka.size()/2; ++i)
                     ~~^~~~~~~~~~~~~
palindromic.cpp: In function 'void setIO(std::__cxx11::string)':
palindromic.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen((s+".in").c_str(),"r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen((s+".out").c_str(),"w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 392 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 432 KB Output is correct
10 Correct 9 ms 896 KB Output is correct
11 Correct 7 ms 768 KB Output is correct
12 Correct 8 ms 768 KB Output is correct
13 Correct 8 ms 640 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 392 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 432 KB Output is correct
10 Correct 9 ms 896 KB Output is correct
11 Correct 7 ms 768 KB Output is correct
12 Correct 8 ms 768 KB Output is correct
13 Correct 8 ms 640 KB Output is correct
14 Correct 352 ms 39696 KB Output is correct
15 Correct 169 ms 34588 KB Output is correct
16 Correct 385 ms 40360 KB Output is correct
17 Correct 197 ms 20868 KB Output is correct