# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
955647 | vjudge1 | Palindromic Partitions (CEOI17_palindromic) | C++17 | 100 ms | 19088 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define gsn "Palindromic Partitions"
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r)
{
return uniform_int_distribution<ll> (l, r) (rng);
}
const int maxn = 1000005;
const int base = 31;
const ll mod = 1000000003ll;
ll Hash[maxn], Pow[maxn];
ll get(int i, int j)
{
return (Hash[j] - Hash[i - 1] * Pow[j - i + 1] + mod * mod) % mod;
}
void solve()
{
string s;
cin >> s;
int n = s.size();
s = ' ' + s;
Pow[0] = 1;
fi(i, 1, n)
{
Pow[i] = Pow[i - 1] * base % mod;
Hash[i] = (Hash[i - 1] * base + s[i] - 'a' + 1) % mod;
}
int vt1 = 1, vt2 = n, ans = 0;
for(int i = 1; i <= vt2; i ++)
{
if(get(vt1, i) == get(vt2 - (i - vt1), vt2))
{
if(i < vt2 - (i - vt1)) ans += 2;
else ans += 1;
vt2 = vt2 - (i - vt1) - 1, vt1 = i + 1;
}
}
if(vt1 <= vt2) ans ++;
cout << ans << '\n';
}
int main()
{
if(fopen(gsn".inp", "r"))
{
freopen(gsn".inp", "r", stdin);
freopen(gsn".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int nTest = 1;
cin >> nTest;
while(nTest --)
{
solve();
}
/// ------------------check time!-----------------///
cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |