oj.uz

Submission #199680

# Submission time Handle Problem Language Result Execution time Memory
199680 2020-02-02T17:49:45 Z rKrPaN Palindromic Partitions (CEOI17_palindromic) C++
60 / 100
 63 ms 5972 KB 
#include <iostream>
#include <string>

using namespace std;

long long H[100100];
long long pot[100100];

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 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 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 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 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 6 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 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 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 6 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 504 KB Output is correct
12 Correct 10 ms 504 KB Output is correct
13 Correct 9 ms 508 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 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 6 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 504 KB Output is correct
12 Correct 10 ms 504 KB Output is correct
13 Correct 9 ms 508 KB Output is correct
14 Runtime error 63 ms 5972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -