oj.uz

Submission #768267

# Submission time Handle Problem Language Result Execution time Memory
768267 2023-06-27T20:40:33 Z NintsiChkhaidze Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 57 ms 20572 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair <int,int>
#define left (h<<1),l,((l + r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define int ll
using namespace std;

const int N = 1e6 + 5,mod = 1e9 + 7;

int pwr[N];

signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int Q;
	cin>>Q;
	
	int k = 31;
	pwr[0] = 1;
	for (int i = 1; i <= 1000000; i++)
		pwr[i] = (pwr[i - 1] * k) % mod;
		
	for (int i= 1; i <= Q; i++){
		string s;
		cin>>s;
		
		int l = 0,r = s.size() - 1;
		int len = 0,ans=0,h1=0,h2 = 0;
		while (l < r){
			++len;
			
			h1 = (h1 + pwr[len] * (s[l] - 'a' + 1))%mod;
			h2 = (h2 * k % mod + (s[r] - 'a' + 1)*k) %mod;
			
			if (h1 == h2) {
				ans += 2;
				h1 = h2 = 0;
				len = 0;
			}
			++l,--r;
		}
		
		if (l == r) ++len;
		if (len) ++ans;
		cout<<ans<<endl;
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8132 KB Output is correct
2 Correct 8 ms 8148 KB Output is correct
3 Correct 7 ms 8048 KB Output is correct
4 Correct 7 ms 8068 KB Output is correct
5 Correct 7 ms 8020 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8132 KB Output is correct
2 Correct 8 ms 8148 KB Output is correct
3 Correct 7 ms 8048 KB Output is correct
4 Correct 7 ms 8068 KB Output is correct
5 Correct 7 ms 8020 KB Output is correct
6 Correct 7 ms 8028 KB Output is correct
7 Correct 7 ms 8084 KB Output is correct
8 Correct 7 ms 8132 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 7 ms 8132 KB Output is correct
2 Correct 8 ms 8148 KB Output is correct
3 Correct 7 ms 8048 KB Output is correct
4 Correct 7 ms 8068 KB Output is correct
5 Correct 7 ms 8020 KB Output is correct
6 Correct 7 ms 8028 KB Output is correct
7 Correct 7 ms 8084 KB Output is correct
8 Correct 7 ms 8132 KB Output is correct
9 Correct 7 ms 8148 KB Output is correct
10 Correct 8 ms 8156 KB Output is correct
11 Correct 7 ms 8148 KB Output is correct
12 Correct 8 ms 8256 KB Output is correct
13 Correct 7 ms 8148 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8132 KB Output is correct
2 Correct 8 ms 8148 KB Output is correct
3 Correct 7 ms 8048 KB Output is correct
4 Correct 7 ms 8068 KB Output is correct
5 Correct 7 ms 8020 KB Output is correct
6 Correct 7 ms 8028 KB Output is correct
7 Correct 7 ms 8084 KB Output is correct
8 Correct 7 ms 8132 KB Output is correct
9 Correct 7 ms 8148 KB Output is correct
10 Correct 8 ms 8156 KB Output is correct
11 Correct 7 ms 8148 KB Output is correct
12 Correct 8 ms 8256 KB Output is correct
13 Correct 7 ms 8148 KB Output is correct
14 Correct 52 ms 20572 KB Output is correct
15 Correct 34 ms 15552 KB Output is correct
16 Correct 57 ms 19756 KB Output is correct
17 Correct 29 ms 14648 KB Output is correct