Submission #983121

#TimeUsernameProblemLanguageResultExecution timeMemory
983121kh0iPalindromic Partitions (CEOI17_palindromic)C++17
0 / 100
1 ms344 KiB
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) #endif using ll = long long; using pii = pair<int, int>; #define F first #define S second #define sz(x) (int)((x).size()) #define all(x) (x).begin(), (x).end() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll get_rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll> (l, r)(rng); } struct Hash{ ll base, mod; int n; string s; vector<ll> p, hash; void precalc(int _n){ hash.resize(_n + 2, 0); p.resize(_n + 2, 0); p[0] = 1; for(int i = 1; i <= _n; ++i) p[i] = (p[i - 1] * base) % mod; } void init(string x, ll _base, ll _mod){ n = x.size(); base = _base, mod = _mod; precalc(n); s = ' ' + x; for(int i = 1; i <= n; ++i) hash[i] = (hash[i - 1] * base + (s[i] - 'a' + 1)) % mod; } ll get_hash(int l, int r){ return (hash[r] - hash[l - 1] * p[r - l + 1] + mod * mod) % mod; } ll get_single_hash(string x){ ll res = 0; for(int i = 0; i < sz(x); ++i) res = (res * base + (x[i] - 'a' + 1)) % mod; return res; } }; void solve(){ string s; cin >> s; Hash h1, h2; h1.init(s, 137, 1e9 + 7); h2.init(s, 137, 1e9 + 9); int l = 1, r = sz(s); int res = 0; while(true){ bool found = 0; for(int len = 1; l + len - 1 < r - len + 1; ++len){ bool ok = 1; ok &= (h1.get_hash(l, l + len - 1) == h1.get_hash(r - len + 1, r)); ok &= (h2.get_hash(l, l + len - 1) == h2.get_hash(r - len + 1, r)); if(ok){ res += 2; l = l + len, r = r - len; found = 1; break; } } if(!found){ ++res; break; } } cout << res << '\n'; } int32_t main() { cin.tie(nullptr)->sync_with_stdio(0); #define task "troll" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; cin >> test; for(int i = 1; i <= test; ++i){ // cout << "Case #" << i << ": "; solve(); } #ifdef LOCAL cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; #endif return 0; }

Compilation message (stderr)

palindromic.cpp: In function 'int32_t main()':
palindromic.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...