oj.uz

Submission #530109

# Submission time Handle Problem Language Result Execution time Memory
530109 2022-02-24T15:43:24 Z fatemetmhr Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 863 ms 484 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 = 4e3 + 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 2 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 2 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 25 ms 332 KB Output is correct
7 Correct 31 ms 312 KB Output is correct
8 Correct 19 ms 372 KB Output is correct
9 Correct 28 ms 332 KB Output is correct
10 Correct 19 ms 368 KB Output is correct
11 Correct 19 ms 332 KB Output is correct
12 Correct 19 ms 372 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 2 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 25 ms 332 KB Output is correct
7 Correct 31 ms 312 KB Output is correct
8 Correct 19 ms 372 KB Output is correct
9 Correct 28 ms 332 KB Output is correct
10 Correct 19 ms 368 KB Output is correct
11 Correct 19 ms 332 KB Output is correct
12 Correct 19 ms 372 KB Output is correct
13 Partially correct 715 ms 484 KB Output is partially correct
14 Partially correct 863 ms 480 KB Output is partially correct
15 Incorrect 628 ms 476 KB Output isn't correct
16 Halted 0 ms 0 KB -