oj.uz

Submission #530112

# Submission time Handle Problem Language Result Execution time Memory
530112 2022-02-24T15:46:25 Z fatemetmhr Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 584 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();
	fill(lcp, lcp + n, 0);
	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(true){
		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 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 204 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 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 20 ms 332 KB Output is correct
7 Correct 25 ms 332 KB Output is correct
8 Correct 18 ms 356 KB Output is correct
9 Correct 26 ms 364 KB Output is correct
10 Correct 19 ms 360 KB Output is correct
11 Correct 22 ms 360 KB Output is correct
12 Correct 20 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 2 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 20 ms 332 KB Output is correct
7 Correct 25 ms 332 KB Output is correct
8 Correct 18 ms 356 KB Output is correct
9 Correct 26 ms 364 KB Output is correct
10 Correct 19 ms 360 KB Output is correct
11 Correct 22 ms 360 KB Output is correct
12 Correct 20 ms 332 KB Output is correct
13 Correct 1187 ms 484 KB Output is correct
14 Execution timed out 1557 ms 584 KB Time limit exceeded
15 Halted 0 ms 0 KB -