oj.uz

Submission #125010

# Submission time Handle Problem Language Result Execution time Memory
125010 2019-07-04T11:03:44 Z gs14004 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 499 ms 35728 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
using lint = long long;
using pi = pair<int, int>;
 
struct dap{
	int x, y, z;
	bool operator<(const dap &d)const{
		return z < d.z;
	}
};
 
int n, m;
string s, t;
int lcp[MAXN][MAXN];
int sx[MAXN];
int sy[MAXN];

vector<int> getfail(string s){
	vector<int> fail(s.size() + 1);
	int p = 0;
	for(int i=1; i<s.size(); i++){
		while(p && s[p] != s[i]) p = fail[p];
		if(s[p] == s[i]) p++;
		fail[i + 1] = p;
	}
	return fail;
}

dap solve(){
	for(int i=n-1; i>=0; i--){
		for(int j=m-1; j>=0; j--){
			if(s[i] == t[j]) lcp[i][j] = lcp[i+1][j+1] + 1;
			else lcp[i][j] = 0;
		}
	}
	memset(sx, 0x3f, sizeof(sx));
	memset(sy, 0x3f, sizeof(sy));
	dap ret = {-1, -1, -1};

	for(int i=n; i>=0; i--){
		string str;
		for(int j=i-1; j>=0; j--) str.push_back(s[j]);
		str.push_back('$');
		for(int j=m-1; j>=0; j--) str.push_back(t[j]);
		vector<int> f = getfail(str);

		memset(sy, 0x3f, sizeof(sy));
		for(int j=0; j<=m; j++){
			sy[lcp[i][j] + j] = min(sy[lcp[i][j] + j], j);
			sx[j] = min(sx[j], i - f.back());
			f.pop_back();
		}
		for(int j=m; j>=0; j--){
			sy[j] = min(sy[j], sy[j + 1]);
			int minsx = sx[j];
			int minsy = sy[j];
			ret = max(ret, (dap){minsx, minsy, i + j - minsx - minsy});
		}
	}
	return ret;
}
 
int main(){
	cin >> s >> t;
	n = s.size();
	m = t.size();
	auto ret = solve();
	reverse(t.begin(), t.end());
	auto y = solve();
	y.y = m - y.y - y.z;
	ret = max(ret, y);
	cout << ret.z << endl;
	cout << ret.x << " " << ret.y << endl;
}

Compilation message

necklace.cpp: In function 'std::vector<int> getfail(std::__cxx11::string)':
necklace.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<s.size(); i++){
               ~^~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 13 ms 2552 KB Output is correct
7 Correct 13 ms 2552 KB Output is correct
8 Correct 12 ms 2424 KB Output is correct
9 Correct 12 ms 2552 KB Output is correct
10 Correct 12 ms 2552 KB Output is correct
11 Correct 13 ms 2552 KB Output is correct
12 Correct 14 ms 2552 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 13 ms 2552 KB Output is correct
7 Correct 13 ms 2552 KB Output is correct
8 Correct 12 ms 2424 KB Output is correct
9 Correct 12 ms 2552 KB Output is correct
10 Correct 12 ms 2552 KB Output is correct
11 Correct 13 ms 2552 KB Output is correct
12 Correct 14 ms 2552 KB Output is correct
13 Correct 499 ms 35728 KB Output is correct
14 Correct 483 ms 35704 KB Output is correct
15 Correct 498 ms 34552 KB Output is correct
16 Correct 486 ms 35700 KB Output is correct
17 Correct 449 ms 35192 KB Output is correct
18 Correct 481 ms 35576 KB Output is correct
19 Correct 468 ms 35576 KB Output is correct
20 Correct 467 ms 35192 KB Output is correct
21 Correct 478 ms 35320 KB Output is correct