oj.uz

Submission #586395

# Submission time Handle Problem Language Result Execution time Memory
586395 2022-06-30T08:23:41 Z Do_you_copy Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 162 ms 42564 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

using ll = long long;
using pii = pair <int, int>;

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
const ll Mod2 = 1000000007;
const int maxN = 1e6 + 2;
int n;
int base = 29;
ll pre[2][maxN], suf[2][maxN], power[2][maxN];
string s;

ll gethash(int l, int r, int t){
    ll tem = pre[t][r] - pre[t][l - 1] * power[t][r - l + 1];
    if (t) return (tem % Mod2 + Mod2) % Mod2;
    return (tem % Mod + Mod) % Mod;
}

bool cmp(int l1, int r1, int l2, int r2){
    return gethash(l1, r1, 1) == gethash(l2, r2, 1)
    && gethash(l1, r1, 0) == gethash(l2, r2, 0);
}


void Init(){
    cin >> s;
    n = s.length();
    for (int i = 1; i <= n; ++i){
        pre[0][i] = pre[0][i - 1] * base + (s[i - 1] - 'a');
        pre[1][i] = pre[1][i - 1] * base + (s[i - 1] - 'a');
        pre[0][i] %= Mod;
        pre[1][i] %= Mod2;
    }
    ll ans = 0;
    int i = 1, j = n;
    while (i <= j){
        int l = i, r = j;
        while (!cmp(i, l, r, j)){
            ++l, --r;
        }
        if (l < r) ans += 2;
        else ++ans;
        i = l + 1, j = r - 1;
    }
    cout << ans << "\n";
}

int main(){
    if (fopen(taskname".txt", "r")){
        freopen(taskname".txt", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    faster
    power[0][0] = power[1][0] = 1;
    for (int i = 1; i <= 1e6 + 1; ++i){
        power[0][i] = power[0][i - 1] * base % Mod;
        power[1][i] = power[1][i - 1] * base % Mod2;
    }
    //freopen(taskname.inp, "r", stdin)
    //freopen(taskname.out, "w", stdout)
    int tt; cin >> tt; while (tt--)
    Init();
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15956 KB Output is correct
2 Correct 12 ms 15972 KB Output is correct
3 Correct 11 ms 15896 KB Output is correct
4 Correct 11 ms 15956 KB Output is correct
5 Correct 11 ms 15984 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15956 KB Output is correct
2 Correct 12 ms 15972 KB Output is correct
3 Correct 11 ms 15896 KB Output is correct
4 Correct 11 ms 15956 KB Output is correct
5 Correct 11 ms 15984 KB Output is correct
6 Correct 11 ms 15956 KB Output is correct
7 Correct 13 ms 15912 KB Output is correct
8 Correct 14 ms 15948 KB Output is correct
9 Correct 13 ms 15956 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15956 KB Output is correct
2 Correct 12 ms 15972 KB Output is correct
3 Correct 11 ms 15896 KB Output is correct
4 Correct 11 ms 15956 KB Output is correct
5 Correct 11 ms 15984 KB Output is correct
6 Correct 11 ms 15956 KB Output is correct
7 Correct 13 ms 15912 KB Output is correct
8 Correct 14 ms 15948 KB Output is correct
9 Correct 13 ms 15956 KB Output is correct
10 Correct 14 ms 16324 KB Output is correct
11 Correct 13 ms 16212 KB Output is correct
12 Correct 12 ms 16248 KB Output is correct
13 Correct 13 ms 16148 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15956 KB Output is correct
2 Correct 12 ms 15972 KB Output is correct
3 Correct 11 ms 15896 KB Output is correct
4 Correct 11 ms 15956 KB Output is correct
5 Correct 11 ms 15984 KB Output is correct
6 Correct 11 ms 15956 KB Output is correct
7 Correct 13 ms 15912 KB Output is correct
8 Correct 14 ms 15948 KB Output is correct
9 Correct 13 ms 15956 KB Output is correct
10 Correct 14 ms 16324 KB Output is correct
11 Correct 13 ms 16212 KB Output is correct
12 Correct 12 ms 16248 KB Output is correct
13 Correct 13 ms 16148 KB Output is correct
14 Correct 162 ms 42564 KB Output is correct
15 Correct 89 ms 37840 KB Output is correct
16 Correct 136 ms 42004 KB Output is correct
17 Correct 90 ms 29948 KB Output is correct