oj.uz

Submission #402688

# Submission time Handle Problem Language Result Execution time Memory
402688 2021-05-12T09:04:56 Z Nicholas_Patrick Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 464 ms 71076 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];
		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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Partially correct 1 ms 332 KB Output is partially correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 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 1 ms 332 KB Output is correct
2 Partially correct 1 ms 332 KB Output is partially correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 8 ms 1612 KB Output is correct
7 Partially correct 10 ms 1612 KB Output is partially correct
8 Correct 7 ms 1356 KB Output is correct
9 Correct 7 ms 1516 KB Output is correct
10 Correct 7 ms 1548 KB Output is correct
11 Correct 7 ms 1576 KB Output is correct
12 Correct 7 ms 1496 KB Output is correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Partially correct 1 ms 332 KB Output is partially correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 8 ms 1612 KB Output is correct
7 Partially correct 10 ms 1612 KB Output is partially correct
8 Correct 7 ms 1356 KB Output is correct
9 Correct 7 ms 1516 KB Output is correct
10 Correct 7 ms 1548 KB Output is correct
11 Correct 7 ms 1576 KB Output is correct
12 Correct 7 ms 1496 KB Output is correct
13 Partially correct 413 ms 71052 KB Output is partially correct
14 Correct 421 ms 71076 KB Output is correct
15 Correct 400 ms 66852 KB Output is correct
16 Correct 464 ms 70016 KB Output is correct
17 Correct 390 ms 68504 KB Output is correct
18 Correct 400 ms 70500 KB Output is correct
19 Correct 395 ms 70544 KB Output is correct
20 Correct 434 ms 68672 KB Output is correct
21 Correct 388 ms 69248 KB Output is correct