oj.uz

Submission #402694

# Submission time Handle Problem Language Result Execution time Memory
402694 2021-05-12T09:11:27 Z Nicholas_Patrick Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 665 ms 71104 KB 
#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>0 and s[c]!=s[i])
			c=ret[c]-1;
		if(c<0)c=0;
		c+=s[c]==s[i];
	}
	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

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:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i=0; i<=s.size(); i++){
      |               ~^~~~~~~~~~
necklace.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0; i<=t.size(); i++){
      |               ~^~~~~~~~~~
necklace.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0; i<=s.size(); i++)for(int j=0; j<=t.size(); j++)
      |               ~^~~~~~~~~~
necklace.cpp:48:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0; i<=s.size(); i++)for(int j=0; j<=t.size(); j++)
      |                                             ~^~~~~~~~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Partially correct 2 ms 332 KB Output is partially correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Partially correct 2 ms 332 KB Output is partially correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 11 ms 1612 KB Output is correct
7 Partially correct 11 ms 1548 KB Output is partially correct
8 Correct 9 ms 1356 KB Output is correct
9 Correct 10 ms 1516 KB Output is correct
10 Correct 11 ms 1508 KB Output is correct
11 Correct 11 ms 1572 KB Output is correct
12 Correct 10 ms 1496 KB Output is correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Partially correct 2 ms 332 KB Output is partially correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 11 ms 1612 KB Output is correct
7 Partially correct 11 ms 1548 KB Output is partially correct
8 Correct 9 ms 1356 KB Output is correct
9 Correct 10 ms 1516 KB Output is correct
10 Correct 11 ms 1508 KB Output is correct
11 Correct 11 ms 1572 KB Output is correct
12 Correct 10 ms 1496 KB Output is correct
13 Partially correct 665 ms 71104 KB Output is partially correct
14 Correct 615 ms 70960 KB Output is correct
15 Correct 594 ms 66904 KB Output is correct
16 Correct 594 ms 69904 KB Output is correct
17 Correct 597 ms 68588 KB Output is correct
18 Correct 616 ms 70600 KB Output is correct
19 Correct 606 ms 70416 KB Output is correct
20 Correct 622 ms 68416 KB Output is correct
21 Correct 597 ms 69180 KB Output is correct