oj.uz

Submission #341421

# Submission time Handle Problem Language Result Execution time Memory
341421 2020-12-29T16:20:30 Z codebuster_10 Palinilap (COI16_palinilap) C++17
17 / 100
 1000 ms 8200 KB 
#include <bits/stdc++.h>

using namespace std ;

#define int long long 
#define ld long double
#define f(i,a,b) for(int i=a;i<b;++i)

#define endl '\n'
#define debug cout<<"\n========================================\n";
#define err1(a) cout<<#a<<" "<<a<<endl;
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl;
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl;
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl;

#define PQ priority_queue
#define LB lower_bound  
#define UB upper_bound
#define fr first
#define sc second

#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define show(a) {for(auto xyz:a)cout<<xyz<<" ";cout<<endl;}
#define sz(x) (int)(x).size()

void setIO(string s = "") {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	if(sz(s)){
		freopen((s+".in").c_str(),"r",stdin);
		freopen((s+".out").c_str(),"w",stdout);
  }
}
/**
 * Description: Polynomial hash for substrings with two bases.
 * Source:
  * BENQ, own modifications
	* KACTL
	* https://codeforces.com/contest/1207/submission/59309672
 * Verification: https://codeforces.com/contest/835/submission/102412420
 */
#define int long long // this is imp
const int MOD = 1e9 + 9 ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> BDIST(0.1*MOD,0.9*MOD);
const array<int,2> base = {BDIST(rng), BDIST(rng)};
 
vector<array<int,2>> pows = {{1,1}};
struct HashRange {
	string S; 
  vector< array<int,2> > cum = {{0,0}};
	void add(char c) { 
    S += c; 
    cum.push_back( { (base[0] * cum.back()[0] + c )%MOD, (base[1] * cum.back()[1] + c )%MOD } ); 
  }
	void add(string s) { 
    for(auto c:s) add(c); 
  }
	void extend(int len) { 
    while ((int)(pows.size()) <= len) {
      pows.push_back({ (base[0] * pows.back()[0])%MOD, (base[1] * pows.back()[1])%MOD });
    } 
  }
	array<int,2> hash(int l, int r) { // 0 based indexing
    int len = r+1-l; extend(len);
		return { ((cum[r+1][0] - pows[len][0] * cum[l][0])%MOD + MOD)%MOD,  ((cum[r+1][1] - pows[len][1] * cum[l][1])%MOD + MOD)%MOD }; 
  }
};
signed main(){
  setIO();
  string st; cin >> st ;
  auto get = [&](string s){
    string rs = s ; reverse(all(rs)) ;
    HashRange S, RS ; S.add(s) ; RS.add(rs) ;
    int cnt = 1, n = sz(s) ; 
    for(int i=1; i<n; ++i){
      // solve for odd len 
      {
        int lo = 1, hi = min(i+1, n-i) + 1 ;
        while(hi-lo>1){
          int mid = (hi+lo)/2 ;
          int s1 = i, e1 = i + mid - 1 ;
          int s2 = n - i - 1 , e2 = n - (i - mid + 1) - 1 ;
          array<int,2> h1 = S.hash(s1, e1), h2 = RS.hash(s2, e2) ;
          h1[0] == h2[0] &&  h1[1] == h2[1] ? lo = mid : hi = mid ;
        } 
        cnt += lo ;
      }
      // solve for even len 
      if(s[i] == s[i-1]){
        int lo = 1, hi = min(i, n-i) + 1 ;
        while(hi-lo>1){
          int mid = (hi+lo)/2 ;
          int s1 = i, e1 = i + mid - 1 ;
          int s2 = n - (i-1) - 1 , e2 = n - (i - mid) - 1 ;
          array<int,2> h1 = S.hash(s1, e1), h2 = RS.hash(s2, e2) ;
          h1[0] == h2[0] &&  h1[1] == h2[1] ? lo = mid : hi = mid ;
        } 
        cnt += lo ;
      }
    }
    return cnt ;
  };
  int ans = 0 ;
  for(int i=0; i<sz(st); ++i){
    for(char c='a'; c<='z'; ++c){
      string temp = st ;
      temp[i] = c ;
      ans = max(ans, get(temp)) ;
    }
  }
  cout << ans ;
}

Compilation message

palinilap.cpp: In function 'void setIO(std::string)':
palinilap.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   freopen((s+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 364 KB Output is correct
2 Correct 53 ms 364 KB Output is correct
3 Correct 41 ms 364 KB Output is correct
4 Correct 37 ms 364 KB Output is correct
5 Correct 31 ms 380 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 1160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 8200 KB Time limit exceeded
2 Halted 0 ms 0 KB -