Submission #865600

#	Time	Username	Problem	Language	Result	Execution time	Memory
865600		pcc	Lampice (COCI19_lampice)	C++14	25 / 110	888 ms	1380 KiB

lampice

#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 (stderr)

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
• Subtask 2: 25 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37