oj.uz

Submission #916496

# Submission time Handle Problem Language Result Execution time Memory
916496 2024-01-26T02:27:36 Z penguin133 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 224 ms 93200 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

string s;
const int mod = 1e9 + 9, mod2 = 1e17 + 5;
int memo[305][305];

int slv(int l, int r){
	if(l > r)return 0;
	if(l == r)return 1;
	//if(memo[l][r] != -1)return memo[l][r];
	int cur = 1, cur2 = 1, cnt = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0;
	int ans = 1;
	string t, t2;
	for(int i = l, j = r; i <= j; i++, j--){
		
		cnt = cnt * 31 + (s[i] - 'a' + 1);
		cnt3 = cnt3 * 31 + (s[i] - 'a' + 1);
		cnt2 += cur * (s[j] - 'a' + 1);
		cnt4 += cur2 * (s[j] - 'a' + 1);
		cur *= 31; cur %= mod; cur2 *= 31; cur2 %= mod2;
		cnt %= mod; cnt2 %= mod; cnt3 %= mod2; cnt4 %= mod2;
		
		//t += s[i]; t2 = s[j] + t2;
		//if(t == t2)return slv(i + 1, j - 1) + 2;
		if(cnt == cnt2 && cnt3 == cnt4)return slv(i + 1, j - 1) + 2;
	}
	return ans;
}

void solve(){
	cin >> s;
	cout << slv(0, (int)s.length() - 1) << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

palindromic.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main(){
      | ^~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 224 ms 93200 KB Output is correct
15 Correct 71 ms 61420 KB Output is correct
16 Correct 42 ms 10736 KB Output is correct
17 Correct 143 ms 28652 KB Output is correct