oj.uz

Submission #955647

# Submission time Handle Problem Language Result Execution time Memory
955647 2024-03-31T08:31:12 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 100 ms 19088 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 600 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 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 600 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 600 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 100 ms 19088 KB Output is correct
15 Correct 61 ms 18408 KB Output is correct
16 Correct 94 ms 18304 KB Output is correct
17 Correct 55 ms 10884 KB Output is correct