oj.uz

Submission #402695

# Submission time Handle Problem Language Result Execution time Memory
402695 2021-05-12T09:12:55 Z Nicholas_Patrick Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 450 ms 71060 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 and s[c]!=s[i])
			c=ret[c-1];
		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:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i=0; i<=s.size(); i++){
      |               ~^~~~~~~~~~
necklace.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<=t.size(); i++){
      |               ~^~~~~~~~~~
necklace.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=0; i<=s.size(); i++)for(int j=0; j<=t.size(); j++)
      |               ~^~~~~~~~~~
necklace.cpp:47:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=0; i<=s.size(); i++)for(int j=0; j<=t.size(); j++)
      |                                             ~^~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 8 ms 1616 KB Output is correct
7 Correct 7 ms 1548 KB Output is correct
8 Correct 8 ms 1356 KB Output is correct
9 Correct 7 ms 1484 KB Output is correct
10 Correct 7 ms 1540 KB Output is correct
11 Correct 9 ms 1572 KB Output is correct
12 Correct 7 ms 1496 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 8 ms 1616 KB Output is correct
7 Correct 7 ms 1548 KB Output is correct
8 Correct 8 ms 1356 KB Output is correct
9 Correct 7 ms 1484 KB Output is correct
10 Correct 7 ms 1540 KB Output is correct
11 Correct 9 ms 1572 KB Output is correct
12 Correct 7 ms 1496 KB Output is correct
13 Correct 441 ms 71012 KB Output is correct
14 Correct 395 ms 71060 KB Output is correct
15 Correct 445 ms 67168 KB Output is correct
16 Correct 423 ms 69968 KB Output is correct
17 Correct 372 ms 68508 KB Output is correct
18 Correct 450 ms 70500 KB Output is correct
19 Correct 398 ms 70444 KB Output is correct
20 Correct 410 ms 68344 KB Output is correct
21 Correct 418 ms 69208 KB Output is correct