Submission #402688

#	Time	Username	Problem	Language	Result	Execution time	Memory
402688		Nicholas_Patrick	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	17 / 85	464 ms	71076 KiB

necklace

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

struct ans{
	int l, a, b;
	ans(int l, int a, int b):l(l), a(a), b(b){}
	bool operator<(ans rhs)const{
		return l<rhs.l;
	}
};
vector<int> zalgo(const string& s){
	if(s.empty())
		return {0};
	vector<int> ret(s.size());
	ret[0]=0;
	for(int i=1; i<s.size(); i++){
		int& c=ret[i]=ret[i-1];
		while(c and s[c]!=s[i])
			c=ret[c];
		c+=s[c]==s[i];
		if(c==i)
			c--;
	}
	return ret;
}
ans solve(const string& s, const string& t){
	vector<vector<int>> tz, sz;
	tz.reserve(s.size()+1);
	sz.reserve(t.size()+1);
	for(int i=0; i<=s.size(); i++){
		string u{s.begin()+i, s.end()};
		u+=' ';
		u+=t;
		auto z=zalgo(u);
		tz.push_back(vector<int>{z.begin()+(s.size()-i), z.end()});
	}
	for(int i=0; i<=t.size(); i++){
		string u{t.begin()+i, t.end()};
		u+=' ';
		u+=s;
		auto z=zalgo(u);
		sz.push_back(vector<int>{z.begin()+(t.size()-i), z.end()});
	}
	ans ret(0, 0, 0);
	for(int i=0; i<=s.size(); i++)for(int j=0; j<=t.size(); j++)
		ret=max(ret, ans(sz[j][i]+tz[i][j], i-sz[j][i], j-tz[i][j]));
	return ret;
}
int main(){
	string s, t;
	cin>>s>>t;
	ans rec1=solve(s, t);
	reverse(t.begin(), t.end());
	ans rec2=solve(s, t);
	rec2.b=t.size()-(rec2.b+rec2.l);
	rec1=max(rec1, rec2);
	printf("%d\n%d %d\n", rec1.l, rec1.a, rec1.b);
}

Compilation message (stderr)

necklace.cpp: In function 'std::vector<int> zalgo(const string&)':
necklace.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=1; i<s.size(); i++){
      |               ~^~~~~~~~~
necklace.cpp: In function 'ans solve(const string&, const string&)':
necklace.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0; i<=s.size(); i++){
      |               ~^~~~~~~~~~
necklace.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i=0; i<=t.size(); i++){
      |               ~^~~~~~~~~~
necklace.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0; i<=s.size(); i++)for(int j=0; j<=t.size(); j++)
      |               ~^~~~~~~~~~
necklace.cpp:49:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0; i<=s.size(); i++)for(int j=0; j<=t.size(); j++)
      |                                             ~^~~~~~~~~~

• Subtask 1: 5 / 25
• Subtask 2: 4 / 20
• Subtask 3: 8 / 40