oj.uz

Submission #710618

# Submission time Handle Problem Language Result Execution time Memory
710618 2023-03-15T12:26:23 Z WonderfulWhale Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 46 ms 11044 KB 
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

const int CNST = 31;
const int MOD = 1e9+7;
int pot[1000009];

int solve(string a) {
	int h1 = 0;
	int h2 = 0;
	int s = 0;
	int e = sz(a)-1;
	int cur = 0;
	int ans = 0;
	int S = 0;
	int E = 0;
	while(s<e) {
		h1 += (a[s]-'a'+1)*pot[cur];
		h1 %= MOD;
		h2 *= CNST;
		h2 += (a[e]-'a'+1);
		h2 %= MOD;
		if(h1==h2) {
			h1 = h2 = cur = 0;
			ans+=2;
			S = s;
			E = e;
		} else {
			cur++;
		}
		s++;
		e--;
	}
	return ans+(S+1!=E);
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	pot[0] = 1;
	for(int i=1;i<1000009;i++) pot[i]=pot[i-1]*CNST%MOD;
	
	int t;
	cin >> t;
	while(t--) {
		string s;
		cin >> s;
		cout << solve(s) << "\n";
	}
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8020 KB Output is correct
2 Correct 9 ms 8052 KB Output is correct
3 Correct 8 ms 8092 KB Output is correct
4 Correct 8 ms 8020 KB Output is correct
5 Correct 8 ms 8020 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 8 ms 8148 KB Output is correct
8 Correct 7 ms 8148 KB Output is correct
9 Correct 7 ms 8148 KB Output is correct
10 Correct 9 ms 8148 KB Output is correct
11 Correct 8 ms 8148 KB Output is correct
12 Correct 8 ms 8148 KB Output is correct
13 Correct 9 ms 8148 KB Output is correct
14 Correct 46 ms 11044 KB Output is correct
15 Correct 32 ms 10884 KB Output is correct
16 Correct 44 ms 10956 KB Output is correct
17 Correct 30 ms 9684 KB Output is correct