oj.uz

Submission #916437

# Submission time Handle Problem Language Result Execution time Memory
916437 2024-01-25T22:22:50 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 38 ms 5404 KB 
#include <algorithm>
#include <cstring>
#include "assert.h"
#include "stdio.h"
 
#define MAX_WORD_LENGTH 5100000
 
int longest_palindromic_partition(char *word) {
	const int n = strlen(word);
	const unsigned int base = 131;  // Prime larger than ord('z')
 
	int done_chars = 0;  // Number of chars processed (greedily) on each side.
	int n_chunks = 0;  // Number of chunks produced so far.
 
	while (done_chars * 2 < n) {
		unsigned int left_hash=0, right_hash=0;  // Hashes of left and right chunks.
		unsigned int base_power=1;  // `base` to the power of (chunk_size - 1).
		for (int chunk_size=1; true; chunk_size++) {
			const int left_chunk_start = done_chars;
			const int right_chunk_start = n - done_chars - chunk_size;
			if (left_chunk_start + chunk_size - 1 >= right_chunk_start) {
				// Left and right chunk overlap; we have to merge them into a final center chunk.
				return n_chunks + 1;
			}
			// Left hash: "ab" -> "abc": 'a'*B^0 + 'b'*B^1 -> 'a'*B^0 + 'b'*B^1 + 'c'*B^2
			base_power = chunk_size == 1 ? 1 : base_power * base;
			left_hash += static_cast<unsigned int>(word[left_chunk_start + chunk_size - 1]) * base_power; 
			// Right hash: "bc" -> "abc": 'b'*B^0 + 'c'*B^1 -> 'a'*B^0 + 'b'*B^1 + 'c'*B^2
			right_hash = static_cast<unsigned int>(word[right_chunk_start]) + right_hash * base;
			if (left_hash == right_hash && strncmp(word + left_chunk_start, word + right_chunk_start, chunk_size) == 0) {
				// We found a good chunk.
				n_chunks += 2;
				done_chars += chunk_size;
				break;
			}
		}
	}
 
	return n_chunks;
}
 
int main() {
	int n;
	char word[MAX_WORD_LENGTH];
	scanf("%d\n", &n);	
	for (int i=0; i<n; i++) {
		scanf("%s\n", word);
		assert(strlen(word) <= MAX_WORD_LENGTH);
		printf("%d\n", longest_palindromic_partition(word));
	}
	return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d\n", &n);
      |  ~~~~~^~~~~~~~~~~~
palindromic.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%s\n", word);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5208 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5236 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 38 ms 5404 KB Output is correct
15 Correct 20 ms 5208 KB Output is correct
16 Correct 29 ms 5212 KB Output is correct
17 Correct 23 ms 5212 KB Output is correct