oj.uz

Submission #1095040

# Submission time Handle Problem Language Result Execution time Memory
1095040 2024-10-01T07:54:05 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 194 ms 20568 KB 
#include<bits/stdc++.h>
#define ll long long
#define ii pair < int , int >
#define iii pair < int , ii>
#define iv pair < ii , ii >
#define fi first
#define se second
#define y1 dkjfd
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 310;

int pre[N], pw[N];

int mul(int x, int y)
{
    return 1LL * x * y % mod;
}
int add(int x, int y)
{
    return ((1LL * x + y) % mod + mod) % mod;
}

int get(int l, int r)
{
    return add(pre[r], - mul(pre[l - 1], pw[r - l + 1]));
}

main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("wormsort.in" , "r" , stdin);
    // freopen("wormsort.out" , "w" , stdout);

    pw[0] = 1;
    for(int i = 1; i <= 1e6; i++)
        pw[i] = mul(pw[i - 1], base);

    int t; cin >> t;
    while(t--)
    {
        string s; cin >> s;
        int n = s.size();
        s = '#' + s;
        
        for(int i = 1; i <= n; i++)
            pre[i] = add(mul(pre[i - 1], base), s[i]);

        int ans = 0;
        int i = 1;
        int d = 1;
        while(true)
        {
            while(get(i, i + d - 1) != get(n - i - d + 2, n - i + 1)) d++;
            // cout << i << " " << d << endl;
            if(i != n - i - d + 2) ans += 2;
            else ans += 1;
            i += d;
            d = 1;
            if(i > (n + 1) / 2) break;
        }
        cout << ans << '\n';
    }
    
    
}

Compilation message

palindromic.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main()
      | ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4188 KB Output is correct
2 Correct 7 ms 4164 KB Output is correct
3 Correct 7 ms 4308 KB Output is correct
4 Correct 6 ms 4188 KB Output is correct
5 Correct 7 ms 4376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4188 KB Output is correct
2 Correct 7 ms 4164 KB Output is correct
3 Correct 7 ms 4308 KB Output is correct
4 Correct 6 ms 4188 KB Output is correct
5 Correct 7 ms 4376 KB Output is correct
6 Correct 7 ms 4188 KB Output is correct
7 Correct 6 ms 4188 KB Output is correct
8 Correct 8 ms 4372 KB Output is correct
9 Correct 7 ms 4184 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4188 KB Output is correct
2 Correct 7 ms 4164 KB Output is correct
3 Correct 7 ms 4308 KB Output is correct
4 Correct 6 ms 4188 KB Output is correct
5 Correct 7 ms 4376 KB Output is correct
6 Correct 7 ms 4188 KB Output is correct
7 Correct 6 ms 4188 KB Output is correct
8 Correct 8 ms 4372 KB Output is correct
9 Correct 7 ms 4184 KB Output is correct
10 Correct 9 ms 4444 KB Output is correct
11 Correct 7 ms 4480 KB Output is correct
12 Correct 8 ms 4440 KB Output is correct
13 Correct 9 ms 4380 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4188 KB Output is correct
2 Correct 7 ms 4164 KB Output is correct
3 Correct 7 ms 4308 KB Output is correct
4 Correct 6 ms 4188 KB Output is correct
5 Correct 7 ms 4376 KB Output is correct
6 Correct 7 ms 4188 KB Output is correct
7 Correct 6 ms 4188 KB Output is correct
8 Correct 8 ms 4372 KB Output is correct
9 Correct 7 ms 4184 KB Output is correct
10 Correct 9 ms 4444 KB Output is correct
11 Correct 7 ms 4480 KB Output is correct
12 Correct 8 ms 4440 KB Output is correct
13 Correct 9 ms 4380 KB Output is correct
14 Correct 194 ms 20568 KB Output is correct
15 Correct 109 ms 15540 KB Output is correct
16 Correct 180 ms 19640 KB Output is correct
17 Correct 108 ms 12924 KB Output is correct