oj.uz

Submission #199681

# Submission time Handle Problem Language Result Execution time Memory
199681 2020-02-02T17:50:58 Z rKrPaN Palindromic Partitions (CEOI17_palindromic) C++
100 / 100
 568 ms 19148 KB 
#include <iostream>
#include <string>

using namespace std;

long long H[1000100];
long long pot[1000100];

long long h(int l, int d){
	l++; d++;
	return H[d] - H[l-1] * pot[d-l+1];
}

int main(){

	int t;
	cin >> t;
	for (int ij = 0; ij < t; ij++){
		
		string s;
		cin >> s;
		
		int n = s.size();
		
		H[1] = s[0]-'a';
		pot[1] = 37;
		int p = 1;
		for (int i = 2; i <= n; i++){
			H[i] = 37*H[i-1] + s[i-1]-'a';
			pot[i] = pot[i-1] * 37;
		}
		int sol = 1;
		
		int d = 1, o = 0;
		for (int i = 0; i < n/2; i++){
			
			long long hl = h(o, o + d-1);
			long long hd = h(n-o-d, n-o-1);
		/*
			cout << d << " " << o << "\n";
			cout << sol << "\n";
			cout << hl << " " << hd << "\n";
		*/	
			if (hl == hd){
				o += d;
				d = 0;
				sol+= 2;
			}
			
			d++;
		}
		if (n%2 == 0 && d == 1)sol--;
		cout << sol << "\n";
		
	}
	return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:27:7: warning: unused variable 'p' [-Wunused-variable]
   int p = 1;
       ^

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 11 ms 504 KB Output is correct
11 Correct 8 ms 552 KB Output is correct
12 Correct 10 ms 504 KB Output is correct
13 Correct 11 ms 504 KB Output is correct
14 Correct 568 ms 19120 KB Output is correct
15 Correct 299 ms 19148 KB Output is correct
16 Correct 510 ms 18356 KB Output is correct
17 Correct 294 ms 10192 KB Output is correct