oj.uz

Submission #37019

# Submission time Handle Problem Language Result Execution time Memory
37019 2017-12-20T13:36:50 Z DoanPhuDuc Palindromic Partitions (CEOI17_palindromic) C++
100 / 100
 113 ms 18616 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 1e6 + 10;
const int B = 1e5 + 7;

int n;

LL H[N], pw[N];

char S[N];

LL Hash(int l, int r) {
    return H[r] - H[l - 1] * pw[r - l + 1];
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    int TC; scanf("%d", &TC);
    pw[0] = 1;
    FOR(i, 1, 1000000) pw[i] = pw[i - 1] * B;
    while (TC--) {
        scanf("%s", S + 1); n = strlen(S + 1);
        FOR(i, 1, n) H[i] = H[i - 1] * B + (S[i] - 'a' + 1);
        int i = 1, p = n, ans = 0;
        FOD(j, n, 1) {
            if (S[i] == S[j]) {
                int L = p - j + 1;
                if (Hash(i, i + L - 1) == Hash(j, j + L - 1)) {
                    if (i + L - 1 >= j) {
                        ans++;
                        break;
                    } else {
                        ans += 2;
                        i = i + L;
                        p = j - 1;
                        if (i > p) break;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:33:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int TC; scanf("%d", &TC);
                             ^
palindromic.cpp:37:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", S + 1); n = strlen(S + 1);
                           ^

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18616 KB Output is correct
2 Correct 6 ms 18616 KB Output is correct
3 Correct 0 ms 18616 KB Output is correct
4 Correct 3 ms 18616 KB Output is correct
5 Correct 0 ms 18616 KB Output is correct
6 Correct 6 ms 18616 KB Output is correct
7 Correct 3 ms 18616 KB Output is correct
8 Correct 3 ms 18616 KB Output is correct
9 Correct 0 ms 18616 KB Output is correct
10 Correct 0 ms 18616 KB Output is correct
11 Correct 3 ms 18616 KB Output is correct
12 Correct 0 ms 18616 KB Output is correct
13 Correct 3 ms 18616 KB Output is correct
14 Correct 113 ms 18616 KB Output is correct
15 Correct 56 ms 18616 KB Output is correct
16 Correct 86 ms 18616 KB Output is correct
17 Correct 69 ms 18616 KB Output is correct