oj.uz

Submission #865600

# Submission time Handle Problem Language Result Execution time Memory
865600 2023-10-24T11:57:27 Z pcc Lampice (COCI19_lampice) C++14
25 / 110
 888 ms 1380 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2e5+10;
int len[mxn];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	string ss,s;
	cin>>n>>ss;
	s = '#';
	for(auto &i:ss)s += i,s += '#';
	len[0] = 0;
	int cen = 0;
	for(int i = 1;i<s.size();i++){
		int p = cen*2-i;
		if(cen+len[cen]<i){
			cen = i;
			while(i-len[i]-1>=0&&i+len[i]+1<s.size()&&s[i+len[i]+1] == s[i-len[i]-1])len[i]++;
		}
		else if(i+len[p] == cen+len[cen]){
			cen = i;
			while(i-len[i]-1>=0&&i+len[i]+1<s.size()&&s[i+len[i]+1] == s[i-len[i]-1])len[i]++;
		}
		else if(i+len[p]<cen+len[cen])len[i] = len[p];
		else len[i] = cen+len[cen]-i;
	}
	int ans = 0;
	//cout<<s<<endl;for(int i = 0;i<=s.size();i++)cout<<len[i]<<' ';cout<<endl;
	for(int i= 0;i<s.size();i++){
		ans = max(ans,len[i]);
	}
	cout<<ans;
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 1;i<s.size();i++){
      |                ~^~~~~~~~~
lampice.cpp:28:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    while(i-len[i]-1>=0&&i+len[i]+1<s.size()&&s[i+len[i]+1] == s[i-len[i]-1])len[i]++;
      |                         ~~~~~~~~~~^~~~~~~~~
lampice.cpp:32:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    while(i-len[i]-1>=0&&i+len[i]+1<s.size()&&s[i+len[i]+1] == s[i-len[i]-1])len[i]++;
      |                         ~~~~~~~~~~^~~~~~~~~
lampice.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i= 0;i<s.size();i++){
      |               ~^~~~~~~~~

Subtask #1
0 / 17.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 992 KB Output is correct
5 Correct 1 ms 1368 KB Output is correct
6 Correct 888 ms 1380 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

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