oj.uz

Submission #35072

# Submission time Handle Problem Language Result Execution time Memory
35072 2017-11-17T22:28:50 Z model_code Palindromic Partitions (CEOI17_palindromic) C++11
100 / 100
 56 ms 5972 KB 
// Greedy solution with rolling string hashes. Repeatedly takes the smallest possible
// chunk from the sides, using string hashes to quickly check for equality of chunks.
// Hash updating and comparison takes O(1), so the total running time is O(n).

#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:49:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d\n", &n); 
                   ^
palindromic.cpp:51:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s\n", word);
                      ^

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5964 KB Output is correct
2 Correct 0 ms 5972 KB Output is correct
3 Correct 0 ms 5972 KB Output is correct
4 Correct 0 ms 5968 KB Output is correct
5 Correct 0 ms 5972 KB Output is correct
6 Correct 0 ms 5968 KB Output is correct
7 Correct 0 ms 5972 KB Output is correct
8 Correct 0 ms 5972 KB Output is correct
9 Correct 0 ms 5972 KB Output is correct
10 Correct 0 ms 5972 KB Output is correct
11 Correct 0 ms 5968 KB Output is correct
12 Correct 0 ms 5968 KB Output is correct
13 Correct 0 ms 5968 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5964 KB Output is correct
2 Correct 0 ms 5972 KB Output is correct
3 Correct 0 ms 5972 KB Output is correct
4 Correct 0 ms 5968 KB Output is correct
5 Correct 0 ms 5972 KB Output is correct
6 Correct 0 ms 5968 KB Output is correct
7 Correct 0 ms 5972 KB Output is correct
8 Correct 0 ms 5972 KB Output is correct
9 Correct 0 ms 5972 KB Output is correct
10 Correct 0 ms 5972 KB Output is correct
11 Correct 0 ms 5968 KB Output is correct
12 Correct 0 ms 5968 KB Output is correct
13 Correct 0 ms 5968 KB Output is correct
14 Correct 49 ms 5972 KB Output is correct
15 Correct 23 ms 5968 KB Output is correct
16 Correct 56 ms 5972 KB Output is correct
17 Correct 43 ms 5972 KB Output is correct