oj.uz

답안 #915863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915863 2024-01-24T19:34:10 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 291 ms 18972 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define pb push_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll sz = 1e6+5, mod = 1e9+7, P = 47;
ll p[sz], h[sz], n, i;
bool check(ll a, ll b, ll k)
{
    ll h1 = (h[a + k - 1] - h[a - 1] + mod) % mod;
    ll h2 = (h[b + k - 1] - h[b - 1] + mod) % mod;
    return (h1 * 1LL * p[b - a]) % mod == h2;
}
int main()
{
    ll tests = 1;
    cin >> tests;
    while(tests--)
    {
        string s;
        cin >> s;
        n = s.size();
        p[0] = 1;
        for(i = 1; i <= n; i++)
            p[i] = (p[i-1] * P * 1LL) % mod;
        for(i = 1; i <= n; i++)
            h[i] = (h[i-1] + ((s[i - 1] - 'a' + 1) * 1LL * p[i-1])) % mod;
        ll ans = 0, l = 1, r = n, k = 1, curl = -1, curr = -1;
        while(l < r)
        {
            ll a = l - k + 1;
            if(check(a, r, k))
            {
                ans++;
                k = 1;
                curl = l;
                curr = r;
            }
            else
                k++;
            l++;
            r--;
        }
        if(curl + 1 == curr)
            cout << ans * 2 << "\n";
        else
            cout << ans * 2 + 1 << "\n";
        for(i = 0; i <= n; i++)
        {
            h[i] = 0;
            p[i] = 0;
        }
        n = 0;
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 4 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 4 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct
14 Correct 291 ms 18972 KB Output is correct
15 Correct 153 ms 18816 KB Output is correct
16 Correct 266 ms 18580 KB Output is correct
17 Correct 147 ms 12316 KB Output is correct