oj.uz

Submission #241583

# Submission time Handle Problem Language Result Execution time Memory
241583 2020-06-24T15:02:43 Z ruler Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 48 ms 19092 KB 
// IOI 2021
 
#include <bits/stdc++.h>
using namespace std;

#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
#define debug(x) cerr << #x << ": " << x << endl
#define debugP(p) cerr << #p << ": {" << p.first << ", " << p.second << '}' << endl
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e9, MOD = INF + 7;
 
/////////////////////////////////////////////////////////////////////
 
const int N = 1e6 + 5, BASE = 619;

string s;
int n, h[N], pw[N];

// [l, r)
int hsh(int l, int r) {
	return h[r] - h[l] * pw[r - l];
}

// [l, r]
int solve(int l, int r) {
	int len = r - l + 1;
	for (int i = 1; i <= len; i++) {
		if (l >= r - i + 1) return 1;
		if (hsh(l, l + i) == hsh(r + 1 - i, r + 1)) return 2 + solve(l + i, r - i);
	}
	return 0;
}

void MAIN() {
	cin >> s;
	n = sz(s);
	for(int i = 0; i < n; i++) h[i + 1] = (h[i] * BASE) + ((int) s[i]);
	cout << solve(0, n - 1) << endl;
}

int main() {
 
	sync;

	pw[0] = 1;
	for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * BASE;
	int t = 1; cin >> t;
	while(t--) MAIN();

	return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4224 KB Output is correct
3 Correct 8 ms 4224 KB Output is correct
4 Correct 7 ms 4224 KB Output is correct
5 Correct 9 ms 4224 KB Output is correct
6 Correct 7 ms 4224 KB Output is correct
7 Correct 8 ms 4224 KB Output is correct
8 Correct 9 ms 4224 KB Output is correct
9 Correct 8 ms 4224 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 8 ms 4352 KB Output is correct
12 Correct 8 ms 4352 KB Output is correct
13 Correct 8 ms 4352 KB Output is correct
14 Correct 48 ms 19092 KB Output is correct
15 Correct 34 ms 14484 KB Output is correct
16 Correct 48 ms 18452 KB Output is correct
17 Correct 30 ms 12052 KB Output is correct