oj.uz

Submission #289941

# Submission time Handle Problem Language Result Execution time Memory
289941 2020-09-03T08:50:48 Z secretweapon Palindromes (APIO14_palindrome) C++14
0 / 100
 255 ms 131076 KB 
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <iostream>

#define N 600005 

using namespace std;

int P[N] = {0};
map <string,int> mp;
string tmp= "", str, nw_str;

int main() {
   
   	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	while(cin>>str) {
	
		memset(P,0,sizeof(P));
		mp.clear();
		// pre processing 
		tmp = "$";
		for(int i=0; i<str.size(); i++) {
			tmp += "#";
			tmp += str[i];
		}
		tmp += "#";
		tmp += "@";
		
		int c = 1;
		int r = 2;
		int n = tmp.size();
		int mx = 1;
		int val;
		int idx, l, cnt;
		
		for(int i=2; i<n-1; i++) {
			idx = 2*c - i;
			P[i] = (i > r) ? 0 : ((P[idx]>(r-i)) ? r-i : P[idx]);
			while(tmp[i-P[i]]==tmp[i+P[i]]) {
				
				nw_str = tmp.substr(i-P[i],2*P[i]+1);
				cnt = mp[nw_str]++;
				//cout<<tmp.substr(i-l,l*2+1)<<endl;
				val = (cnt+1)*P[i];
				mx = (mx < val) ? val : mx;
				P[i]++;
			}
			P[i]--;
			if((i+P[i])>r) {
				r = i + P[i];
				c = i;
			}
		}
		cout<<mx<<endl;
	}
	return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i=0; i<str.size(); i++) {
      |                ~^~~~~~~~~~~
palindrome.cpp:38:12: warning: unused variable 'l' [-Wunused-variable]
   38 |   int idx, l, cnt;
      |            ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Incorrect 2 ms 2688 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 242 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 255 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -