oj.uz

Submission #618795

# Submission time Handle Problem Language Result Execution time Memory
618795 2022-08-02T07:32:36 Z nghiass001 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 102 ms 28680 KB 
#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define REPD(i, r, l) for(int i = (r) - 1; i >= (l); --i)
using namespace std;

typedef unsigned long long ull;
const int N = 1e6 + 5;
const ull base = 27;
int t, n;
string s;
ull B[N], H[N];

void Enter() {
    cin >> s;
    n = s.length();
    s = ' ' + s;
}

ull getHash(int l, int r) {
    return H[r] - H[l - 1] * B[r - l + 1];
}

void Process() {
    B[0] = 1;
    FOR(i, 1, n) B[i] = B[i - 1] * base;
    FOR(i, 1, n) H[i] = H[i - 1] * base + s[i] - 'a' + 1;
    int res = (n == 1), len = 0;
    FOR(i, 1, n/2) {
        int j = i;
        while (j <= n/2 && getHash(i, j) != getHash(n - j + 1, n - i + 1)) ++j;
        i = j;
        if (i > n/2) { ++res; break; }
        res += 2;
        if (i * 2 + 1 == n) ++res;
    }
    cout << res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    if (fopen("palindromic.inp", "r")) freopen("palindromic.inp", "r", stdin);
    cin >> t;
    while (t--) {
        Enter();
        Process();
    }
}

Compilation message

palindromic.cpp: In function 'void Process()':
palindromic.cpp:29:25: warning: unused variable 'len' [-Wunused-variable]
   29 |     int res = (n == 1), len = 0;
      |                         ^~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:44:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     if (fopen("palindromic.inp", "r")) freopen("palindromic.inp", "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 102 ms 27636 KB Output is correct
15 Correct 53 ms 22860 KB Output is correct
16 Correct 99 ms 28680 KB Output is correct
17 Correct 54 ms 14668 KB Output is correct