oj.uz

Submission #43241

# Submission time Handle Problem Language Result Execution time Memory
43241 2018-03-11T09:43:36 Z krauch Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 504 ms 25196 KB 
/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair < ll, int > PLI;


#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

#define fname ""

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 2e6 + 6;

int n, d[N], mn[N];
int hs[N], p[N], pr = 37;
char a[N], b[N];

int get(int l, int r) {
    return (hs[r] - 1ll * hs[l - 1] * p[r - l + 1] % base + base) % base;
}

int calc(int i) {
    if (i == n / 2 + 1) return (n & 1);
    int len = 0;
    forn(j, 1, n / 2 - i + 1) {
        if (get(i, i + j - 1) == get(n - i - j + 2, n - i + 1)) {
            len = j;
            break;
        }
    }
    if (len) return calc(i + len) + 2;
    return 1;
}

int main() {
	#ifdef krauch
        freopen("input.txt", "r", stdin);
    #else
        //freopen(fname".in", "r", stdin);
        //freopen(fname".out", "w", stdout);
    #endif

    int T;
    scanf("%d\n", &T);
    while (T--) {
        string s;
        getline(cin, s);
        n = sz(s);
        p[0] = 1;
        forn(i, 1, n) {
            a[i] = s[i - 1];
            hs[i] = (1ll * hs[i - 1] * pr + a[i] - 'a') % base;
            p[i] = 1ll * p[i - 1] * pr % base;
        }
        cout << calc(1) << "\n";
    }

	return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:74:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", &T);
                      ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 2 ms 556 KB Output is correct
5 Correct 2 ms 556 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 2 ms 556 KB Output is correct
5 Correct 2 ms 556 KB Output is correct
6 Correct 2 ms 556 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 2 ms 556 KB Output is correct
9 Correct 2 ms 556 KB Output is correct
10 Correct 6 ms 712 KB Output is correct
11 Correct 5 ms 732 KB Output is correct
12 Correct 6 ms 732 KB Output is correct
13 Correct 5 ms 732 KB Output is correct
14 Correct 504 ms 12484 KB Output is correct
15 Correct 293 ms 15396 KB Output is correct
16 Correct 454 ms 24644 KB Output is correct
17 Correct 269 ms 25196 KB Output is correct