oj.uz

Submission #530110

# Submission time Handle Problem Language Result Execution time Memory
530110 2022-02-24T15:44:10 Z fatemetmhr Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 846 ms 592 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define fi     first
#define se     second
#define all(x) x.begin(), x.end()

const int maxn5 = 7e3 + 10;

int n, m;

string z;
vector <pair<int, int>> av, qu;
int l[maxn5], lp[maxn5], lcp[maxn5];


inline void find_lcp(){
	int n = z.size();
	memset(lcp, 0, sizeof lcp);
	int l = 0, r = 0;
	//cout << "alright " << z << endl;
	for(int i = 1; i < n; i++){
		if(i <= r)
			lcp[i] = min(r - i + 1, lcp[i - l]);
		//cout << i << ' ' << l << ' ' << r << ' ' << lcp[i] << endl;
		while(i + lcp[i] < n && z[lcp[i]] == z[i + lcp[i]])
			lcp[i]++;
		if(i + lcp[i] - 1 > r){
			l = i;
			r = i + lcp[i] - 1;
		}
		//cout << i << ' ' << lcp[i] << endl;
	}
	return;
}

inline pair<int, pair<int, int>> solve(string s, string t){
	
	//cout << "wow! " << endl;
	n = s.size(); 
	m = t.size();
	string sp = s;
	reverse(sp.begin(), sp.end());
	
	
	int ans = 0, idt, ids;
	
	for(int i = 0; i < m; i++){
		qu.clear();
		av.clear();
		z = "";
		for(int j = i; j < m; j++)
			z.pb(t[j]);
		z = z + "$";
		int id = z.size();
		z = z +  s;
		find_lcp();
		for(int j = 0; j < n; j++)
			l[j] = lcp[j + id];
		z = "";
		for(int j = i - 1; j >= 0; j--)
			z.pb(t[j]);
		z = z + "$";
		id = z.size();
		z = z + sp;
		find_lcp();
		for(int j = 0; j < n; j++)
			lp[j] = lcp[n - j - 1 + id];
		for(int j = 0; j < n; j++){
			//cout << i << ' ' << j << ' ' << l[j] << ' ' << lp[j] << endl;
			qu.pb({l[j] + j, j});
			av.pb({j - lp[j] + 1, j});
		}
		sort(all(qu));
		sort(all(av));
		int ind = 0, mx = -1;
		for(auto [val, id] : qu){
			while(ind < av.size() && av[ind].fi <= val){
				mx = max(mx, av[ind].se);
				ind++;
			}
			if(mx - id + 1 >= ans && mx - id + 1 >= 1){
				ans = mx - id + 1;
				ids = id;
				if(val - id >= ans)
					idt = i;
				else
					idt = i + val - id - 1 - (mx - id + 1) + 1;
			}
		}
	}
	
	return {ans, {ids, idt}};
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	

	string s, t; cin >> s >> t;

	pair <int, pair<int, int>> ans1 = solve(s, t);
	if(int(s.size()) * int(t.size()) <= 1e6){
		reverse(t.begin(), t.end());
		pair <int, pair<int, int>> ans2 = solve(s, t);
		int len = ans2.fi, id = ans2.se.se;
		id = int(t.size()) - id - 1;
		id -= len - 1;
		ans2.se.se = id;
		if(ans1 < ans2)
			ans1 = ans2;
	}
	

	cout << ans1.fi << '\n' << ans1.se.fi << ' ' << ans1.se.se << '\n';

	
}

Compilation message

necklace.cpp: In function 'std::pair<int, std::pair<int, int> > solve(std::string, std::string)':
necklace.cpp:82:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    while(ind < av.size() && av[ind].fi <= val){
      |          ~~~~^~~~~~~~~~~
necklace.cpp:97:25: warning: 'ids' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |  return {ans, {ids, idt}};
      |                         ^
necklace.cpp:97:25: warning: 'idt' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 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 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 29 ms 368 KB Output is correct
7 Correct 27 ms 332 KB Output is correct
8 Correct 23 ms 376 KB Output is correct
9 Correct 28 ms 380 KB Output is correct
10 Correct 21 ms 332 KB Output is correct
11 Correct 23 ms 380 KB Output is correct
12 Correct 21 ms 332 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 29 ms 368 KB Output is correct
7 Correct 27 ms 332 KB Output is correct
8 Correct 23 ms 376 KB Output is correct
9 Correct 28 ms 380 KB Output is correct
10 Correct 21 ms 332 KB Output is correct
11 Correct 23 ms 380 KB Output is correct
12 Correct 21 ms 332 KB Output is correct
13 Partially correct 614 ms 484 KB Output is partially correct
14 Partially correct 785 ms 592 KB Output is partially correct
15 Correct 636 ms 484 KB Output is correct
16 Partially correct 846 ms 496 KB Output is partially correct
17 Incorrect 548 ms 492 KB Output isn't correct
18 Halted 0 ms 0 KB -