oj.uz

Submission #45266

# Submission time Handle Problem Language Result Execution time Memory
45266 2018-04-12T11:36:21 Z qoo2p5 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 41 ms 38856 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

typedef unsigned long long ull;

const int N = (int) 1e6 + 123;
const ull P = 239;

string s;
ull p[N];

void solve() {
	cin >> s;
	int n = sz(s);
	int res = 0;
	ull left = 0;
	ull right = 0;
	int already = 0;
	int len = 0;
	while (already + len < n / 2) {
		int pos_l = already + len;
		int pos_r = n - already - len - 1;
		left = left * P + s[pos_l];
		right += s[pos_r] * p[len];
		len++;
		if (left == right) {
			already += len;
			len = 0;
			left = 0;
			right = 0;
			res += 2;
		}
	}
	
	if (n % 2 == 1 || left != 0) {
		res++;
	}
	
	cout << res << "\n";
}

void run() {
	p[0] = 1;
	rep(i, 1, N) p[i] = p[i - 1] * P;
	
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8228 KB Output is correct
4 Correct 8 ms 8248 KB Output is correct
5 Correct 8 ms 8304 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8228 KB Output is correct
4 Correct 8 ms 8248 KB Output is correct
5 Correct 8 ms 8304 KB Output is correct
6 Correct 8 ms 8476 KB Output is correct
7 Correct 8 ms 8588 KB Output is correct
8 Correct 9 ms 8588 KB Output is correct
9 Correct 8 ms 8588 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8228 KB Output is correct
4 Correct 8 ms 8248 KB Output is correct
5 Correct 8 ms 8304 KB Output is correct
6 Correct 8 ms 8476 KB Output is correct
7 Correct 8 ms 8588 KB Output is correct
8 Correct 9 ms 8588 KB Output is correct
9 Correct 8 ms 8588 KB Output is correct
10 Correct 9 ms 8588 KB Output is correct
11 Correct 8 ms 8620 KB Output is correct
12 Correct 8 ms 8820 KB Output is correct
13 Correct 8 ms 8900 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8228 KB Output is correct
4 Correct 8 ms 8248 KB Output is correct
5 Correct 8 ms 8304 KB Output is correct
6 Correct 8 ms 8476 KB Output is correct
7 Correct 8 ms 8588 KB Output is correct
8 Correct 9 ms 8588 KB Output is correct
9 Correct 8 ms 8588 KB Output is correct
10 Correct 9 ms 8588 KB Output is correct
11 Correct 8 ms 8620 KB Output is correct
12 Correct 8 ms 8820 KB Output is correct
13 Correct 8 ms 8900 KB Output is correct
14 Correct 41 ms 19768 KB Output is correct
15 Correct 27 ms 24964 KB Output is correct
16 Correct 32 ms 34088 KB Output is correct
17 Correct 23 ms 38856 KB Output is correct