oj.uz

Submission #955646

# Submission time Handle Problem Language Result Execution time Memory
955646 2024-03-31T08:31:01 Z Yang8on Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 105 ms 28568 KB 
#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

palindromic.cpp: In function 'int main()':
palindromic.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(gsn".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(gsn".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 708 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 708 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 105 ms 28568 KB Output is correct
15 Correct 60 ms 23520 KB Output is correct
16 Correct 99 ms 27652 KB Output is correct
17 Correct 57 ms 15984 KB Output is correct